P17156 [ICPC 2017 Xi'an R] LOVER II

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.