题目描述

小 S 最近学会了二分图匈牙利匹配算法。

现在二分图的 X 部有 $N$ 个数字 $A_i$，Y 部有 $K$ 个数字 $C_i$。

已知如果 $A_i + C_j \le Z$，那么 $A_i$ 和 $C_j$ 之间就有一条边，求二分图（X，E，Y）的最大匹配数。

小 S 是初学者，所以她想做多做一些练习来巩固知识。于是她找到了一个长度为 $M$ 的正整数数组 $B$，每次她会在 $B$ 数组中抽取一段连续的区间 $[L_i,R_i]$，把区间 $[L_i,R_i]$ 的所有数字作为二分图 Y 部的 $K$ 个数字 $C_i$，然后重新求一次二分图最大匹配数。

小 S 打算一共做 $Q$ 次练习，但是她不知道每次计算出的答案对不对，你能帮帮她吗？

输入格式

第一行为三个正整数 $N,M,Z$。

第二行为 $N$ 个正整数，第 $i$ 个正整数表示 $A_i$。

第三行为 $M$ 个正整数，第 $i$ 个正整数表示 $B_i$。

第四行为一个整数 $Q$ 表示询问个数。

接下来 $Q$ 行每行两个正整数，第 $i$ 行的两个正整数分别表示 $L_i,R_i$。

输出格式

对于每次练习，输出该次练习的答案。

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

提示

对于 $100\%$ 的数据，$1 \le A_i,B_i,Z \le 10^9$，$1 \le L_i \le R_i \le Q$。

保证数据有一定梯度。