Problem Statement

You are given positive integers $N$ and $K$, and two permutations $A = (A_1, A_2, \dots, A_{N+K})$ and $B = (B_1, B_2, \dots, B_{N+K})$ of $(1, 2, \dots, N+K)$. Process $Q$ queries.

For each query, given a pair of integers $(X, Y)$, solve the following problem. (All queries are independent.)

There are $N + K + X$ cards labeled from $1$ to $N + K + X$. Each card has a pair of integers written on it. Specifically,

• For $1 \leq i \leq N+K$, card $i$ has $(A_i, B_i)$.
• For $N + K + 1 \leq i \leq N + K + X$, card $i$ has $(i, Y)$.

At the beginning, you have the $N$ cards $1$ to $N$ in your hand, and the $K + X$ cards from $N+1$ to $N + K + X$ are on the table. You may perform the following sequence of operations any number of times, possibly zero.

• First, choose one card from your hand and one card from the table, calling them card $i$ and card $j$. Here, the following condition must hold:
• Let $(a_i, b_i)$ be the pair of integers written on card $i$, and $(a_j, b_j)$ be the pair on card $j$. You must have $a_i < a_j$ and $b_i < b_j$.
• Then, remove card $j$ from the table and place card $i$ on the table (the removed card is no longer available).

What is the minimum number of cards you can end up holding in your hand after performing these operations?

Constraints

• $1 \leq N \leq 2 \times 10^5$
• $1 \leq K \leq 10$
• $1 \leq Q \leq 2 \times 10^5$
• $1 \leq A_i \leq N + K$
• $1 \leq B_i \leq N + K$
• $A$ and $B$ are permutations of $(1, 2, \dots, N+K)$.
• $1 \leq X \leq 10$
• $1 \leq Y \leq N + K$
• All input values are integers.

Input

The input is given from Standard Input in the following format, where $\mathrm{query}_i$ denotes the $i$-th query:

N K Q
A_1 A_2 \dots A_{N+K}
B_1 B_2 \dots B_{N+K}
\mathrm{query}_1
\mathrm{query}_2
\vdots
\mathrm{query}_Q

Each query is given in the following format:

X Y

Output

Print $Q$ lines. The $i$-th line should contain the answer to the $i$-th query.