Defense of the Ancients

DotA? I’m afraid you’ve got a wrong impression, because we are talking about some real Ancients.
A lot of towers are in the first quadrant of rectangular coordinates. And between every two towers there is a wall. All of them are Ancients. Somehow, some skytroopers are trying to attack our Ancients and all we know is that they’ll land at the second, third and fourth quadrant of rectangular coordinates. Because those areas are desolation, the troops decided to follow a fixed straight line. Now we’ve got all the landing coordinates of the troops and the polar angle of their walking lines. To protect our Ancients, we need to know where the troops will first arrive at the Ancients.

There are multiple test cases.
First line contains a single integer T (T<=10), indicates the number of test cases.
For each test case:
The first line has two positive integers N and M (1<N<=100000, M<=100000), represent the number of towers and skytroopers.
Following N lines, each line contains two integers X and Y, represents the coordinate of the tower.
Following M lines, each line has three integers SX, SY and XITA, indicates the coordinates of a skytrooper and the polar angle of their attacking line (in degrees). SX and SY will not bigger than 0 at the same time.
All the coordinates values lies in [-20000, 20000]. No two towers will be in same place.

For every skytrooper, output one line, if the trooper can reach the Ancients, output the coordinate he will first arrive, otherwise output “safe”.
If the value differs in 0.01 with our standard output, we’ll consider it as accepted.

1
6 3
5 1
8 5
13 2
14 7
7 9
1 7
-2 -2 45
8 -2 90
-3 7 120

3.400000 3.400000
8.000000 1.375000
safe

2009 Multi-University Training Contest 19 - Host by BNU