有一天，$n$ 个女孩和 $m$ 个男孩来到西安寻找伴侣。每个女孩都有一个价值，第 $i$ 个女孩的价值记为 $a[i]$。每个男孩也有一个价值，第 $j$ 个男孩的价值记为 $b[j]$。第 $i$ 个女孩和第 $j$ 个男孩可以相爱，当且仅当 $a[i]+b[j] \ge k$，其中 $k$ 是一个已知的系数。

在此，我们考虑关于他们的一些查询。在每个查询中，你需要判断：如果只考虑编号从 $L$ 到 $R$ 的男孩，是否所有女孩都能找到各自的伴侣，且每个男孩最多只能被一名女孩选择。

输入格式

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

接下来是 $T$ 个测试用例。每个测试用例的第一行包含三个整数 $n, m$ 和 $k$，其中 $1 \le n \le 100000$，$1 \le m \le 200000$，$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 100000$)，表示查询的数量。

接下来的 $q$ 行，每行提供两个整数 $L$ 和 $R$ ($1 \le L \le R \le m$)，对应一个查询。

输出格式

对于每个查询，如果女孩们都能找到各自的伴侣，输出“1”，否则输出“0”。

样例

样例输入 1

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

样例输出 1

1
0