题目描述

One day $n$ girls and $m$ boys come to Xi'an to look for a mate. Each girl has a value $a_i$, each boy has a value $b_i$. Girl $i$ and boy $j$ will fall in love only if $a_i + b_j \ge k$.

Then $q$ queries follow. Ask you to calculate if we only have boys labeled from $L$ to $R$, can we make all girls find their lovers?

输入格式

Several test cases (no more than $10$).

First line an integer $T$ $(1 \le T \le 10)$. Indicates the number of test cases.

Then $T$ test cases follow. Each test case begins with three integers $n, m, k$ $(1 \le n, m \le 2 \times 10^5, 0 \le k \le 10^9)$. The next line has $n$ integers indicating $a_1$ to $a_n$ $(0 \le a_i \le 10^9)$. The next line has $m$ integers indicating $b_1$ to $b_m$ $(0 \le b_i \le 10^9)$.

Then comes an integer $q$. $(1 \le q \le 10^5)$.

The next $q$ lines each contain two integers $L, R$ $(1 \le L \le R \le m)$ indicating each query.

输出格式

For each query, print "1" if we can make it or "0" otherwise.

1
3 4 5
1 1 1
4 4 4 3
2
1 3
2 4

1
0