题目描述

一天，$n$ 个女孩和 $m$ 个男孩来到西安寻找伴侣。每个女孩有一个价值 $a_i$，每个男孩有一个价值 $b_i$。只有当 $a_i + b_j \ge k$ 时，女孩 $i$ 和男孩 $j$ 才会坠入爱河。

随后有 $q$ 个询问。请你计算，如果只使用编号从 $L$ 到 $R$ 的男孩，能否让所有女孩都找到爱人？

输入格式

多组测试数据（不超过 $10$ 组）。

第一行是一个整数 $T$ $(1 \le T \le 10)$，表示测试用例的数量。

随后有 $T$ 组测试数据。每组测试数据以三个整数 $n, m, k$ 开始 $(1 \le n, m \le 2 \times 10^5, 0 \le k \le 10^9)$。接下来一行有 $n$ 个整数，表示 $a_1$ 到 $a_n$ $(0 \le a_i \le 10^9)$。再接下来一行有 $m$ 个整数，表示 $b_1$ 到 $b_m$ $(0 \le b_i \le 10^9)$。

然后是一个整数 $q$。$(1 \le q \le 10^5)$。

接下来的 $q$ 行，每行包含两个整数 $L, R$ $(1 \le L \le R \le m)$，表示每个询问。

输出格式

对于每个查询，如果能够做到则输出 "1"，否则输出 "0"。

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

1
0

提示

翻译由 DeepSeek V4 Pro 完成