考虑 OX 轴从 $$$1$$$ 到 $$$n$$$ 的一段。该路段有 $$$k$$$ 观测塔。
每个塔都有两个参数 - 坐标 $$$x_i$$$ 和高度 $$$h_i$$$。所有塔的坐标都是不同的。从塔$$$i$$$,你可以看到点$$$j$$$,如果$$$|x_i - j| \le h_i$$$ (其中 $$$|a|$$$ 是 $$$a$$$ 的绝对值)。
一枚硬币可以将任何塔的高度增加 $$$1$$$。每个塔的高度可以增加任意次数(包括零)。
您需要处理 $$$q$$$ 独立查询。在第$$$i$$$查询中,给出了两个不同的点$$$l$$$和$$$r$$$。您需要计算能够看到这两个点(从一座塔或从不同塔)所需的最小硬币数量。
输入
第一行包含两个整数 $$$n$$$ 和 $$$k$$$ ($$$2 \le n \le 2 \cdot 10^5$$$; $$$1 \le k \le n$$$) — OX 轴线段的长度和观测塔的数量。
第二行包含 $$$k$$$ 整数 $$$x_1, x_2, \dots, x_k$$$ ($$$1 \le x_i \le n$$$) — 观测塔的坐标。所有塔的坐标都是不同的。
第三行包含 $$$k$$$ 整数 $$$h_1, h_2, \dots, h_k$$$ ($$$0 \le h_i \le n$$$) — 观测塔的高度。
第四行包含一个整数 $$$q$$$ ($$$1 \le q \le 2 \cdot 10^5$$$) — 查询数。
接下来的 $$$q$$$ 行包含两个整数 $$$l$$$ 和 $$$r$$$ ($$$1 \le l < r \le n$$$) - 下一个查询的描述。
输出
对于每个查询,输出一个整数 - 能够看到两个点(来自一个塔或来自不同塔)所需的最小硬币数量。
示例
输入 #1
20 3 2 15 10 6 2 0 3 1 20 10 11 3 4
输出 #1
3 1 0
输入 #2
10 2 2 9 1 2 3 4 5 5 6 1 10
输出 #2
2 2 0