[BJWC2018] 基础匹配算法练习题

小 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

测试数据编号|$N$|$M$|$Q$ :-:|:-:|:-:|:-: $1 \sim 4$|$\le 50$|$\le 50$|$\le 50$ $5 \sim 10$|$\le 2501$|$\le 2501$|$\le 2501$ $11\sim 14$|$\le 152501$|$\le 45678$|$\le 45678$ $15 ,16$|$\le 152501$|$\le 50$|$\le 52501$ $17 \sim 20$|$\le 152501$|$\le 52501$|$\le 52501$ 对于 $100\%$ 的数据，$1 \le A_i,B_i,Z \le 10^9$，$1 \le L_i \le R_i \le Q$。 保证数据有一定梯度。