← 返回题目列表

Codeforces · 877/F

F. 安和书籍

中文机器翻译题面 查看原题

在安最喜欢的书店里有多达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] 的子段。