Akame

Statement:

Akame is training on an infinite 2D Cartesian plane. There is an infinitely long rigid and vertical string at each integer x-coordinate. She takes out her katana, Murasame, and makes N infinitely long slashes on the plane. Each slash can be seen as a line with the equation Ax+By=C , for some A , B , and C . A slash will never be a vertical line.

Each string Akame slashes will immediately be broken into two smaller strings. For example, a string originally from (5,) to (5,) severed by the line 0x+1y=3 will be broken into the two strings (5,) to (5,3) and (5,3) to (5,) . A string is considered disconnected if it is of a finite length. For example, the string from (1,9) to (1,) is not of finite length, but the string from (8,3) to (8,4) is.

There are M points on strings Akame wants to disconnect. A point is said to be disconnected if it is either slashed or the string it's on is disconnected. To measure her performance, Akame would like to know the earliest moment (that is, after which slash) each point is disconnected. The slashes are numbered from 1 to N .

Input:

The first line of input will have N and M , separated by a single space.

The next N lines of input will each describe one of Akame's slashes, with A , B , and C separated by spaces.

The next M lines of input will each describe a point Akame wants to disconnect, with X_i and Y_i .

Output:

There should be M lines of output. The ith line should contain the smallest index of the slash that after it is performed, the ith point is disconnected. If the ith point is never disconnected, print -1 instead.

Constraints:

1N500000

1M500000

0A,|C|30000

1|B|30000

0|X_i|,|Y_i|109

Example input 1
3 5
0 1 3
0 1 5
0 1 7
1 2
1 3
1 4
1 5
1 6
		
Example output 1
-1
1
2
2
3
		
Example input 2
10 10
81 -36 72
64 -69 24
23 47 47
83 36 18
1 25 77
12 -81 -3
13 -90 -34
23 19 -34
19 23 78
50 -96 82
56 59
85 47
46 -23
1 13
-74 -69
23 99
-98 72
-31 -65
-78 76
9 -69
		
Example output 2
2
3
4
-1
2
-1
4
2
4
-1
		
Time and memory limit:

  • 10s
  • 1024MB

Problem source: DMOJ