Description

Xiao S recently learned the Hungarian algorithm for bipartite matching.

Now the X part of a bipartite graph has $N$ numbers $A_i$, and the Y part has $K$ numbers $C_i$.

If $A_i + C_j \le Z$, then there is an edge between $A_i$ and $C_j$. Find the maximum matching size of the bipartite graph $(X, E, Y)$.

Xiao S is a beginner, so she wants to do more practice to consolidate her knowledge. She found a positive integer array $B$ of length $M$. Each time, she picks a continuous subarray $[L_i, R_i]$ from $B$, takes all numbers in $[L_i, R_i]$ as the $K$ numbers $C_i$ on the Y part of the bipartite graph, and then recomputes the maximum matching size.

Xiao S plans to do $Q$ practice sessions, but she is not sure whether each computed answer is correct. Can you help her?

Input Format

The first line contains three positive integers $N, M, Z$.

The second line contains $N$ positive integers, where the $i$-th integer is $A_i$.

The third line contains $M$ positive integers, where the $i$-th integer is $B_i$.

The fourth line contains an integer $Q$ denoting the number of queries.

Each of the next $Q$ lines contains two positive integers; on the $i$-th line, the two integers are $L_i, R_i$.

Output Format

For each practice session, output the answer for that session.

4 10 8
1 2 4 6
6 3 6 2 8 4 9 10 6 8
4
1 4
2 5
5 6
1 6

4
3
1
4

Hint

For $100\%$ of the testdata, $1 \le A_i, B_i, Z \le 10^9$, $1 \le L_i \le R_i \le M$.

The testdata is graded.

Translated by ChatGPT 5