15611번 - Broken Gearbox 스페셜 저지다국어

The mechanical Turk was an 18th-century sham robot designed to give the illusion of artificial intelligence by playing chess. More importantly, the Turk inspired us to make our own fake robot that gives the illusion of real intelligence by solving programming contest problems.

We put some gears on axles inside an uncovered panel to make our machine look more realistic. Since the gears are just for visual effect, they have been placed so as to create an impressive meshing pattern; however, the placement is without any regard to gear ratios or turning direction, so it is possible that none of the gears can really move.

It is guaranteed that every axle was connected to every other axle by meshing, either directly or indirectly. Two axles a and b are said to have directly meshing gears if their distance from one another is equal to the sum of the radii of their gears (d_ab = r_ga + r_gb).

Sadly, the gears fell off our machine. We think we collected all of them back up again, but now we are not sure which should go back on which axle. Please find a way of putting the gears on the axles to make them mesh the way they did originally.

The input consists of:

• One line with an integer n (2 ≤ n ≤ 10⁵), the number of gears and axles.
• One line with n integers r₁ . . . r_n (1 ≤ r_i ≤ 10⁸ for each i), the radius of each gear.
• One line with an integer m (n − 1 ≤ m ≤ 10⁵), the number of pairs of axles to mesh.
• m lines with three integers a_i, b_i, d_i (1 ≤ a < b ≤ n; 1 ≤ d ≤ 10⁸), the indices of two axles that were previously meshed, and the distance between them, respectively.

If the machine can be fixed with the given gears, give any one valid matching by outputting n integers g₁. . .g_n, where g_i is the 1-based index of the gear to put on the i-th axle. Otherwise, output “impossible”.