ENG  RUSTimus Online Judge
Online Judge
Problems
Authors
Online contests
About Online Judge
Frequently asked questions
Site news
Webboard
Links
Problem set
Submit solution
Judge status
Guide
Register
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules

Open Ural FU Championship 2013

About     Problems     Submit solution     Judge status     Standings
Contest is over

G. Nested Segments

Time limit: 1.0 second
Memory limit: 64 MB
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

inputoutput
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
To submit the solution for this problem go to the Problem set: 1987. Nested Segments