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
2013-04-05 17:07:01 Frane Kurtoviæ
No.
2013-04-05 17:05:51 Marko Djokic
Are the conveyor belts in the input always sorted by the Y coordinate?
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.