You are given n segments on a straight line. For each pair of segments
it is known that they either have no common points or all points of one segment
belong to the second segment.
Then m queries follow. Each query represents a point on the line. For each
query, your task is to find the segment of the minimum
length, to which this point belongs.
Input
The first line contains an integer n that is the number of segments (1 ≤ n ≤ 105).
i’th of the next n lines contains integers ai and bi that are
the coordinates of endpoints of the i’th segment (1 ≤ ai < bi ≤ 109).
The segments are ordered by non-decreasing ai, and when ai = aj
they are ordered by decreasing length. All segments are distinct.
The next line contains an integer m that is the number of queries (1 ≤ m ≤ 105).
j’th of the next m lines contains an integer cj that is the coordinate of the point
(1 ≤ cj ≤ 109). The queries are ordered by non-decreasing cj.
Output
For each query output the number of the corresponding segment
on a single line. If the point does not belong to any segment, output “-1”. The
segments are numbered from 1 to n in order they are given in the input.
Sample
input | output |
---|
3
2 10
2 3
5 7
11
1
2
3
4
5
6
7
8
9
10
11
| -1
2
2
1
3
3
3
1
1
1
-1
|
Problem Author: Mikhail Rubinchik, idea by Nikita Pervukhin
Problem Source: Open Ural FU Championship 2013