A. After party in Campinas
time limit per test
2 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

A large music festival featuring many different genres took place in the city of Campinas, attracting visitors from all over the country. However, it is now two o'clock on Sunday morning, and the festival has come to an end. Still full of energy, several groups of visitors decided to look for an after-party to keep the night going.

Fortunately, they found a list of nightclubs open that night in the city, all of which offer an open bar. For each nightclub, the list provides the entrance fee and the predominant music genre.

Since the visitors are unfamiliar with the city, every group will follow the order of the list exactly to find the first nightclub they can attend. Each group has a maximum amount of money they are willing to spend per person and also rejects a particular music genre. Therefore, a group will choose the first nightclub on the list whose entrance fee does not exceed their budget and whose predominant music genre is not the one they reject.

Your task is to determine which nightclub will be chosen by each group of visitors.

Input

The first line contains two integers $$$N$$$ and $$$Q$$$ ($$$1 \leq N, Q \leq 2 \cdot 10^5$$$), representing, respectively, the number of nightclubs in the list and the number of groups of visitors.

The next $$$N$$$ lines describe the nightclubs in the order in which they appear in the list. Each of these lines contains two integers $$$C_i$$$ and $$$S_i$$$ ($$$1 \leq C_i \leq 10^8$$$ and $$$1 \leq S_i \leq 10^8$$$), representing, respectively, the entrance fee of the $$$i$$$-th nightclub and the identifier of its music genre.

The nightclubs are given in non-increasing order of entrance fee, that is, $$$C_1 \geq C_2 \geq \cdots \geq C_N$$$. In the case of equal entrance fees, the relative order between nightclubs is arbitrary.

The next $$$Q$$$ lines describe the groups of visitors. Each of these lines contains two integers $$$D_i$$$ and $$$O_i$$$ ($$$1 \leq D_i \leq 10^8$$$ and $$$1 \leq O_i \leq 10^8$$$), representing, respectively, the maximum amount of money that the $$$i$$$-th group can spend per person and the identifier of the music genre rejected by that group.

Output

For each group, print a line containing the index of the nightclub chosen by that group.

If there is no valid nightclub for a group, print -1.

Examples
Input
5 6
100 1
80 2
80 1
50 3
20 2
90 1
80 2
80 1
50 3
19 1
100 4
Output
2
3
2
5
-1
1
Input
6 7
50 1
40 2
40 3
25 2
10 4
5 1
50 1
40 2
30 2
10 4
4 1
5 2
100 5
Output
2
3
5
6
-1
6
1