在安最喜欢的书店里有多达n 本关于数学和经济学的书。书籍编号从 1 到 n。它们每个都包含非负数的问题。
今天有促销活动:从 l 到 r 的段的任何子段都可以以固定价格购买。
Ann 决定购买这样的非空子段,以便在其上进行销售,并且数学问题的数量比经济学问题的数量正好多出 k。请注意,k 可以是正值、负值或零。
不幸的是,Ann 不确定销售针对哪个细分市场进行,但她有 q 个假设。对于每个人,她想知道购买满足条件的子细分的选项数量(因为她花在选择上的时间取决于此)。
目前安正忙于解决其他问题,她向你寻求帮助。对于每个假设,确定给定段的子段数量,使得数学问题的数量比该子段上的经济学问题的数量正好多 k。
输入
第一行包含两个整数 n 和 k (1 ≤ n ≤ 100 000, - 109 ≤ k ≤ 109) — 书籍数量以及数学问题数量与经济学问题数量之间所需的差值。
第二行包含 n 个整数 t1, t2, ..., tn (1 ≤ ti ≤ 2),其中如果第 i 本书是关于数学的,则 ti 为 1;如果第 i 本书是关于经济学的,则 ti 为 2。
第三行包含 n 个整数 a1, a2, ..., an (0 ≤ ai ≤ 109),其中 ai 是第 i 本书中的问题数。
第四行包含一个整数 q (1 ≤ q ≤ 100 000) — 假设的数量。
接下来的 q 行包含两个整数 li 和 ri (1 ≤ li ≤ ri ≤ n) 描述第 i 个 Ann 的假设。
输出
打印 q 行,其中第 i 行打印第 i 个 Ann 假设的子段数。
示例
输入 #1
4 1 1 1 1 2 1 1 1 1 4 1 2 1 3 1 4 3 4
输出 #1
2 3 4 1
输入 #2
4 0 1 2 1 2 0 0 0 0 1 1 4
输出 #2
10
注意
在第一个样本中,如果子细分 [1;1]、[2;2]、[3;3]、[2;4] 属于销售细分,则 Ann 可以购买它们,因为数学问题的数量比经济学问题的数量大 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] 的子段。