J. Server
time limit per test
1 second
memory limit per test
1024 megabytes
input
standard input
output
standard output

Magner Weira has a server with $$$n$$$ components. Each component works only within a certain temperature range: component $$$i$$$ tolerates temperatures from $$$l_i$$$ to $$$r_i$$$, inclusive. If the temperature leaves this range, the component burns out permanently.

Magner has been so busy that he has neglected the server for $$$m$$$ days. Worried that some components may have burned out, he checks the room's temperature records. The only available record lists the minimum temperature $$$a_j$$$ and maximum temperature $$$b_j$$$ reached on each day $$$j$$$.

For each component, determine the first day on which it burned out, or report that it is still working after these $$$m$$$ days.

Input

The first line contains two integers $$$n$$$ and $$$m$$$ ($$$1 \leq n \leq 10^{5}$$$, $$$1 \leq m \leq 10^{5}$$$), the numbers of components and days.

Each of the next $$$n$$$ lines contains two integers $$$l_i$$$ and $$$r_i$$$ ($$$1 \leq l_i \leq r_i \leq 10^{5}$$$), the temperature limits of component $$$i$$$.

Each of the following $$$m$$$ lines contains two integers $$$a_j$$$ and $$$b_j$$$ ($$$1 \leq a_j \leq b_j \leq 10^{5}$$$), the minimum and maximum temperatures on day $$$j$$$.

Output

Print $$$n$$$ lines. Line $$$i$$$ must contain the first day on which component $$$i$$$ burned out, or $$$-1$$$ if it is still working after all $$$m$$$ days. Days are numbered from $$$1$$$ to $$$m$$$.

Examples
Input
6 4
10 20
1 100
15 16
12 18
5 11
9 18
12 16
14 20
9 17
10 26
Output
3
-1
1
2
1
2
Input
3 2
1 100000
5 5
1 1
5 5
1 5
Output
-1
2
1
Input
4 5
4 9
1 3
8 10
1 10
5 8
4 9
3 10
2 9
1 10
Output
3
1
1
-1
Note

Explanation for example 1

The first component tolerates temperatures between $$$10$$$ and $$$20$$$: it survives the first two days but burns out on the third, when the minimum is $$$9$$$. The third component burns out on the first day because the minimum, $$$12$$$, is below its lower limit of $$$15$$$. The second component tolerates all recorded temperatures.