Problem F
99 Problems

You’re creating problems for competitive programming practical examination, but you’re told your problems are either too hard or too easy. Fortunately, you’ve got 99 problems and coming up with more ain’t one. To decide on suitable problems, you will discard problems based on their difficulty.

After coming up with $N$ problems of difficulty $D_i$, you will be told to discard either

1. The easiest problem strictly harder than difficulty $D$. If you have problems of difficulties $[10,10,11]$ and students find $D=10$ too hard, you will discard $D_i=11$ to get $[10,10]$.

2. The hardest problem not harder than difficulty $D$. If you have problems of difficulties $[10,10,11]$ and students find $D=10$ too easy, you will discard the last $D_i=10$ to get $[10,11]$.

Input

The first line contains two integers $N$ ($1\le N\le 5\times {10}^5$) and $Q$ ($1\le Q\le {10}^5$).

The next line contains $N$ integers of $D_i$ ($1\le D_i\le {10}^9$), the difficulties of the $N$ problems you came up with.

The next $Q$ lines contain two integers $T$ ($1$ or $2$) and $D$ ($1\le D\le {10}^9$). $T$ corresponds to discarding problems strictly harder than ($1$) or not harder than ($2$) $D$.

Output

For each problem discarded, print the difficulty $D_i$ of the problem on a new line. If a problem of the required difficulty does not exist or was previously discarded, print $-1$.

Subtasks

1. ($1$ Points): Sample Input.

2. ($18$ Points): $N\le {10}^4$, $Q\le {10}^4$, $D\le {10}^3$ and $T=1$.

3. ($22$ Points): $N\le {10}^4$, $Q\le {10}^4$ and $D_i\le {10}^3$.

4. ($19$ Points): $Q\le {10}^4$ and $D_i\le {10}^3$.

5. ($25$ Points): $Q\le {10}^4$ and $D_i$ are unique.

6. ($15$ Points): No additional constraints.

Warning

The I/O files are large. Please use fast I/O methods.

3 4
10 10 11
1 10
1 10
1 9
1 5

11
-1
10
10

3 4
10 10 11
2 10
2 10
2 10
2 15

10
10
-1
11