Credit to
for tweaking the problem to be harder.is having trouble with his Latin homework. Since he wants to study for his summatives, he has translated the problem and entrusted you with this task instead.
He has given you segments. Segment
covers the interval
and has a value
. We say that segment
covers segment
if every point in
is inside segment
, and this would still hold true if segment
were shifted to the left or to the right by
. These
segments are special - if two segments share a point, then the larger segment covers the smaller segment.
He gives you queries in the form of
a b
. For each query, find the ID of the segment with lowest value that covers both segments and
. If there are no such segments, output
-1
.
If there is more than one segment that covers and
of the same value, output the one of smallest length.
Please help
solve this problem!Input Specification
A single integer
, followed by
lines in the form
.
The next line will contain a single integer
, followed by
queries in the form
a b
.
Output Specification
lines, the answer to the
query.
Sample Input 1
3
2 3 2
1 6 10
4 5 3
2
1 3
1 2
Sample Output 1
2
-1
Comments
Are the segments distinct?
In other words, there cannot be any two segments that partially share a range (this includes the ends).