Sirius Black, the prisoner of Azkaban wants to find Harry Potter so he tries to escape from the prison cell. The prison cells are arranged in the following manner:
There are two rows of prison cells facing each other, each having $N$ numbers of cells.

Each prison cell has some escape value. Let $E$ be the escape value and $K$ be the index of the prison cell in which Sirius Black is. Sirius Black can escape from a prison cell only if that prison cell is in the opposite row and its escape value is less than or equal to $E$. Further, he can escape from the prison if its index is less than or equal to $K$.
You have to answer $Q$ queries.

Input
First-line contains two space-separated integers $N$ and $Q$.
Second-line contains $N$ space-separated integers $A1_1,A1_2,A1_3,........A1_N$ , escape values of 1st-row's prison cells.
Third-line contains $N$ space-separated integers $A2_1,A2_2,A2_3,........A2_N$, escape values of 2nd-row's prison cells.
Next, $Q$ Line Contain two space-separated integer $T$ and $K$, Where $T$ defines the row number of the prison (can be either 1 or 2) and K defines the index of the prison cell where Sirius Black is.

Output

For each query containing row number 1, print the number of prison cell such that it is less than or equal to $A1[K]$ in the range $A2[1] …..A2[K]$.
For each query containing row number 2, print the number of prison cell such that it is less than or equal to $A2[K]$ in the range $A1[1] ….. A1[K]$.

Constraints
$1 \leq N,Q \leq 10^6\\ 1\leq A1[i], A2[i]\leq10^6\\1\leq K \leq N$