Ann and Books

Description:

Input:

The first line contains two integers n and k (1 ≤ n ≤ 100 000,  - 10⁹ ≤ k ≤ 10⁹) — 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₁, t₂, ..., 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₁, a₂, ..., a_n (0 ≤ a_i ≤ 10⁹), 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.

Output:

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

Sample Input:

4 1
1 1 1 2
1 1 1 1
4
1 2
1 3
1 4
3 4

Sample Output:

2
3
4
1

Sample Input:

4 0
1 2 1 2
0 0 0 0
1
1 4

Sample Output:

10

Note:

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].