CF877F.Ann and Books

In Ann's favorite book shop are as many as n books on math and economics. Books are numbered from 1 to n. Each of them contains non-negative number of problems.

Today there is a sale: any subsegment of a segment from l to r can be bought at a fixed price.

Ann decided that she wants to buy such non-empty subsegment that the sale operates on it and the number of math problems is greater than the number of economics problems exactly by k. Note that k may be positive, negative or zero.

Unfortunately, Ann is not sure on which segment the sale operates, but she has q assumptions. For each of them she wants to know the number of options to buy a subsegment satisfying the condition (because the time she spends on choosing depends on that).

Currently Ann is too busy solving other problems, she asks you for help. For each her assumption determine the number of subsegments of the given segment such that the number of math problems is greaten than the number of economics problems on that subsegment exactly by k.

安的最爱书店里有足足 $n$ 本数学与经济学方面的书籍。这些书编号为 $1$ 到 $n$，每本书包含若干道（非负整数）习题。

今天书店正在举行促销活动：任意位于区间 $[l, r]$ 内的子区间均可按固定价格购买。

安决定购买一个非空子区间，该子区间必须处于促销区间内，且其上数学习题数量比经济学习题数量恰好多 $k$ 道。注意：$k$ 可以为正数、负数或零。

遗憾的是，安并不确定促销活动实际覆盖的区间是哪一个，但她有 $q$ 种猜测。对于每一种猜测，她都想知道满足条件的可购子区间的数量（因为她做选择所花费的时间取决于该数量）。

目前安正忙于解决其他问题，于是请你帮忙。对她的每一种猜测，请计算给定区间 $[l, r]$ 中，有多少个子区间满足：该子区间上的数学习题数量比经济学习题数量恰好多 $k$ 道。

The first line contains two integers n and k (1 ≤ n ≤ 100 000,  - 109 ≤ k ≤ 109) — the number of books and the needed difference between the number of math problems and the number of economics problems.

The second line contains n integers _t_1, _t_2, ..., t__n (1 ≤ t__i ≤ 2), where t__i is 1 if the i-th book is on math or 2 if the i-th is on economics.

The third line contains n integers _a_1, _a_2, ..., a__n (0 ≤ a__i ≤ 109), where a__i is the number of problems in the i-th book.

The fourth line contains a single integer q (1 ≤ q ≤ 100 000) — the number of assumptions.

Each of the next q lines contains two integers l__i and r__i (1 ≤ l__i ≤ r__i ≤ n) describing the i-th Ann's assumption.

第一行包含两个整数 $n$ 和 $k$（$1 \leq n \leq 100\,000$，$-10^9 \leq k \leq 10^9$）——分别表示书的总数以及所需的数学问题数量与经济学问题数量之间的差值。

第二行包含 $n$ 个整数 $t_1,\,t_2,\,...,\,t_n$（$1 \leq t_i \leq 2$），其中 $t_i = 1$ 表示第 $i$ 本书是数学类书籍，$t_i = 2$ 表示第 $i$ 本书是经济学类书籍。

第三行包含 $n$ 个整数 $a_1,\,a_2,\,...,\,a_n$（$0 \leq a_i \leq 10^9$），其中 $a_i$ 表示第 $i$ 本书中问题的数量。

第四行包含一个整数 $q$（$1 \leq q \leq 100\,000$）——表示 Ann 提出的假设数量。

接下来的 $q$ 行中，每行包含两个整数 $l_i$ 和 $r_i$（$1 \leq l_i \leq r_i \leq n$），描述第 $i$ 个假设所对应的区间。

Print q lines, in the i-th of them print the number of subsegments for the i-th Ann's assumption.

输出 q 行，其中第 i 行输出 Ann 的第 i 个假设所对应的子区间数量。

In the first sample Ann can buy subsegments [1;1], [2;2], [3;3], [2;4] if they fall into the sales segment, because the number of math problems is greater by 1 on them that the number of economics problems. So we should count for each assumption the number of these subsegments that are subsegments of the given segment.

Segments [1;1] and [2;2] are subsegments of [1;2].

Segments [1;1], [2;2] and [3;3] are subsegments of [1;3].

Segments [1;1], [2;2], [3;3], [2;4] are subsegments of [1;4].

Segment [3;3] is subsegment of [3;4].

在第一个样例中，如果子区间 [1;1]、[2;2]、[3;3]、[2;4] 落入促销区间，则安可以购买它们，因为这些区间上数学题数量比经济学题数量恰好多 1。因此，对于每种假设，我们都应统计给定区间中满足条件的子区间的数量。

区间 [1;1] 和 [2;2] 是 [1;2] 的子区间。

区间 [1;1]、[2;2] 和 [3;3] 是 [1;3] 的子区间。

区间 [1;1]、[2;2]、[3;3] 和 [2;4] 是 [1;4] 的子区间。

区间 [3;3] 是 [3;4] 的子区间。