F. Аня и книги
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

В любимом магазине Ани продается целых n книг по математике и экономике, пронумерованных от 1 до n. В каждой книге содержится неотрицательное число задач.

Сегодня там проходит акция: любой подотрезок отрезка с l по r можно купить по фиксированной цене.

Аня решила, что хочет купить непустой подотрезок, на который действует акция, такой, что в нем ровно на k задач по математике больше, чем по экономике. Заметьте, что k может быть положительным, отрицательным или нулем.

К сожалению, Аня не уверена, на какой отрезок распространяется акция, но у нее есть q предположений. Для каждого из них она хочет заранее знать количество вариантов купить подотрезок, удовлетворяющий условию (ведь от этого зависит время, которое она потратит на выбор).

Сейчас Аня слишком занята решением других задач, поэтому просит вашей помощи. Определите для каждого предположения, сколько существует подотрезков данного отрезка таких, что задач по математике там ровно на k больше, чем по экономике.

Входные данные

В первой строке содержится два целых числа n и k (1 ≤ n ≤ 100 000,  - 109 ≤ k ≤ 109) — количество книг и необходимая разница количества задач по математике и экономике.

Во второй строке содержится n целых чисел t1, t2, ..., tn (1 ≤ ti ≤ 2), число ti равно 1, если i-я книга по математике и 2, если i-я книга по экономике.

В третьей строке содержится n целых чисел a1, a2, ..., an (0 ≤ ai ≤ 109), где ai — число задач в i-й книге.

В четвертой строке содержится целое число q (1 ≤ q ≤ 100 000) — количество предположений Ани.

В следующих q строках содержится по два целых числа li и ri (1 ≤ li ≤ ri ≤ n) — i-е предположение Ани.

Выходные данные

Выведите q строк, в i-й из которых количество подходящих подотрезков для i-го предположения Ани.

Примеры
Входные данные
4 1
1 1 1 2
1 1 1 1
4
1 2
1 3
1 4
3 4
Выходные данные
2
3
4
1
Входные данные
4 0
1 2 1 2
0 0 0 0
1
1 4
Выходные данные
10
Примечание

В первом примере Ане подойдут подотрезки [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]