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

1697. Sniper Shot

Time limit: 1.0 second
Memory limit: 64 MB
There is a sniper at point S. His mission is to eliminate an enemy of the state, who rides his bicycle along a straight line from point A to point B. The bullet flies along a striaght line with infinite speed. There are n rectangular parallelepiped-shaped skyscrapers in the city. The bullet can't fly through the skyscraper but can touch its border. Of course, the sniper will make a deadly shot as soon as possible. Your task is to calculate the coordinates of the enemy at the moment of the shot.


The first line contains space-separated coordinates of S: sx, sy, sz (sz ≥ 0). The second line contains space-separated coordinates of points A and B: ax, ay, bx, by. The enemy of the state moves on the surface of earth, so his z-coordinate is always equal to zero. The third line containts an integer n (0 ≤ n ≤ 100). Each of the following n lines contains space-separated numbers lx, ly, rx, ry, h (lx < rx; ly < ry; h > 0)—coordinates of the opposite corners of the bottom of the current skyscraper and its height. The sides of the skyscrapers are parallel to the corrdinate axes. All coordinates and heights are integers and don't exceed 100 by their absolute values. It is guaranteed that no two skyscrapers have common points, the point S doesn't lie inside or on the border of the skyscraper and the segment AB doesn't have common points with any of the skyscrapers.


If the enemy of the state cannot be eliminated, output “Impossible”. In the other case output the coordinates of the enemy of the state precise up to 10−7.


0 0 2
-4 4 4 4
-3 2 -1 3 10
1 -1 4 2 20
-1.3333333333 4.0000000000
0 0 2
4 1 4 -1
1 -1 3 1 10
Problem Author: Alex Samsonov
Problem Source: Ural SU Contest. Petrozavodsk Winter Session, February 2009