407635: GYM102861 N Number Multiplication

Eugenius is a very bright mathematician who enjoys multiplying numbers.

Once, he found $$$M$$$ nodes written on a piece of paper, numbered from 1 to $$$M$$$, we call these $$$M$$$-nodes. Each node $$$i$$$ was labeled with a unique prime number $$$p_i$$$, such that the primes were ordered (i.e. if $$$i < j$$$ then $$$p_i < p_j$$$).

Later on, he decided to draw $$$N$$$ new nodes, called $$$N$$$-nodes, and add edges between nodes in $$$M$$$ and nodes in $$$N$$$. He was very careful not to connect an $$$M$$$-node with an $$$M$$$-node, nor an $$$N$$$-node with an $$$N$$$-node; he wasn't as careful regarding how many edges between any two nodes he drew.

And just like that, he ended up with a bipartite multigraph.

As he mainly enjoyed multiplying numbers, he decided to label each $$$N$$$-node with the multiplication of all $$$M$$$-nodes that were directly connected to it; where each $$$M$$$-node was multiplied as many times as edges were between them.

Each $$$N$$$-node $$$i$$$ ended up being labeled with a number $$$c_i$$$. Then, the following formula characterizes each $$$c_i$$$:

$$$$$$ c_i = \prod_{(j,i) \in E} p_j, $$$$$$

where $$$E$$$ is the multiset of added edges, and every edge $$$e$$$ satisfies $$$e \in M \times N$$$. Later on, Eugenius decided to grab something to eat. While he was enjoying his torus, he accidentally spilled coffee on the labels $$$p_i$$$ and they disappeared.

Can you help him recover those sorted prime numbers?

The first line contains three integers $$$M$$$, $$$N$$$ and $$$K$$$, the amount of $$$M$$$-nodes, the amount of $$$N$$$-nodes and the amount of distinct edges. These values are such that $$$1 \le M, N < 10^3$$$ and $$$1 \le K \le 10^4$$$.

The next line has $$$N$$$ numbers $$$c_i$$$ (the labels of the $$$N$$$-nodes), such that $$$1 < c_i < 10^{15}$$$.

Finally, there are $$$K$$$ lines, each of these has three numbers $$$m$$$ $$$n$$$ $$$d$$$, representing that there are $$$d$$$ edges between $$$M$$$-node $$$m$$$ and $$$N$$$-node $$$n$$$, satisfying $$$1 \le m \le M$$$, $$$1 \le n \le N$$$ and $$$1 \le d \le 50$$$.

It is guaranteed that all nodes ($$$M$$$-nodes and $$$N$$$-nodes) have degree at least 1.

Output a single line with $$$M$$$ sorted numbers, the prime labels of the $$$M$$$-nodes of indices $$$1, \ldots, M$$$ that keep Eugenius awake.

4 3 4
15 16 13
2 1 1
3 1 1
1 2 4
4 3 1

2 3 5 13

4 5 7
3 9 7 143 143
1 1 1
1 2 2
2 3 1
3 4 1
3 5 1
4 5 1
4 4 1

3 7 11 13