BALL - The Ball

In a coordinate plane, there are N horizontal conveyor belts, each moving either leftwards or rightwards. When the ball falls on a belt, the belt drags it in direction it's moving. When the ball reaches the end of the belt, it falls vertically downwards. For example, if the belt is moving rightwards and it ends in the unit square with x-coordinate 12, the ball will fall from the belt on the x-coordinate 13, and continue falling on the same x-coordinate until it falls on another belt or reaches the ground (the height of 0).

Frane drops a ball many times (from the height that is greater than any of the belt heights), from various x-coordinates, and your task is: for each ball Frane drops, determine the direction of each belt such that this ball falls on as many belts as possible.

This picture represents the first test example:

Input

In the first line of input, there is an integer N (the number of conveyor belts, 1 ≤ N ≤ 100000).

In each of the next N lines, there are integers X1, X2, Y (X1 ≤ X2, 0 < X1, X2, Y < 109) representing the belt. Imagine the belt as a segment of which the bounding unit squares are (X1, Y) and (X2, Y). The belt's thickness is zero and it lies on the bottom of the given unit squares. The belts will not touch or overlap each other.

In the next line, there is an integer Q (the number of falling balls, 1 ≤ Q ≤ 100000).

In the next Q lines there is an integer less than 109, representing the x-coordinate of the unit square Frane drops the ball from.

Output

For each of the Q queries, output the greatest possible number of the conveyor belts visited by the ball.

Example

Input:
3
1 4 3
5 7 2
2 4 1
4
1
4
5
6

Output:
3
3
2
2
Input:
3
5 20 20
15 30 15
10 14 11
3
5
30
516546

Output:
3
2
0

Added by:Adrian Satja Kurdija
Date:2011-02-21
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:Frane Kurtović

hide comments
2016-07-04 19:01:09
O((N + Q) log 1e9) gets AC, @Alex Abbas

At least it did for me without any optimizations
2015-10-03 15:59:01 Rishav Goyal
time limit is so desperate in this problem! it should be set in a way that problems with Good complexity pass like in Codeforces!

Last edit: 2015-10-03 15:59:20
2015-04-13 20:50:21 Divyanshu Kakwani
My solution seems to work correctly in all the test cases I can imagine. It is still getting WA. Can anybody post some corner cases?
2015-01-23 21:56:45 Alex Abbas
Time limit too strict O(N log n + Q log N) gets TLE
2013-04-11 06:29:17 PetarV
@Uros: It is invalid. If it was possible, then you could configure the belts in such a way to make the first two balls touch infinitely many belts...

Last edit: 2013-04-11 06:30:29
2013-04-09 15:33:04 codeslay0r
@Uros: I believe not, since "The belts will not touch"
2013-04-08 23:06:12 Uros Joksimovic
Is
2
1 1 1
2 2 1
3
1
2
3
A valid input?
2013-04-08 18:46:13 PetarV
@Radostin: There can be, but they may not touch or intersect each other.
@deltaprime: You decide the direction of each conveyor belt, to maximize your solution.
2013-04-08 10:40:45 deltaprime@gmail.com
Is the first conveyor belt always from left to right, and do they always go in order LR - RL - LR ?
2013-04-06 15:20:19 Radostin Chonev
Can there be two conveyor belts on one line ?
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.