ENG  RUSTimus Online Judge
Online Judge
Problems
Authors
Online contests
About Online Judge
Frequently asked questions
Site news
Webboard
Links
Problem set
Submit solution
Judge status
Guide
Register
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules

1632. Lasers

Time limit: 1.0 second
Memory limit: 64 MB
Never before the special agent Ivan Okhotnichii had been so close to a failure. It had seemed that to get into a secret laboratory through a ventilation hole in the ceiling and hack the computer would be no trouble. However, from above Ivan noticed that the laboratory was pierced by N laser beams. Touching any of them would activate the alarm system. The ith beam was generated by an emitter located at the point (Xi, Yi, Zi) and was directed along the vector (ui, vi, wi). Ivan examined the room and determined the numbers Xi and Yi. He also computed the vectors (ui, vi, wi). However, in order to plan his further actions, Ivan had to know the Z coordinates of the emitters as well.
Luckily, for some pairs of laser beams Ivan managed to determine that the first beam in the pair was above the second (that meant that there existed X, Y, Z1, Z2 such that the point (X, Y, Z1) belonged to the first beam, the point (X, Y, Z2) belonged to the second beam, and Z1 was greater than Z2). Help Ivan to find one of the possible arrangements of the lasers in space.

Input

The first line contains the number of lasers N (1 ≤ N ≤ 100). In each of the following N lines, there are the integers Xi, Yi, ui, vi, wi, which describe the ith laser; these numbers are in the range from −100 to 100. In the next line, there is the number M of pairs of lasers for which their relative positions are known (0 ≤ M ≤ 10000). Each of the following M lines contains two different integers i and j, which mean that the ith laser is above the jth laser (1 ≤ i, jN). None of the laser beams is parallel to the OZ axis, and no two beams lie in the same vertical plane.

Output

Output N real numbers, one number per line, which are the coordinates Zi. Their absolute values shouldn't exceed 106. The numbers must be given with the maximal possible accuracy. The existence of at least one arrangement of lasers complying with the input data is guaranteed.

Sample

inputoutput
4
0 0 1 0 0
1 0 0 1 0
1 1 -1 0 0
0 1 0 -1 0
3
1 2
2 3
3 4
4.000
3.000
2.000
1.000
Problem Author: Dmitry Ivankov (prepared by Alex Samsonov)
Problem Source: XIII Open USU Championship