В любимом магазине Ани продается целых n книг по математике и экономике, пронумерованных от 1 до n. В каждой книге содержится неотрицательное число задач.
Сегодня там проходит акция: любой подотрезок отрезка с l по r можно купить по фиксированной цене.
Аня решила, что хочет купить непустой подотрезок, на который действует акция, такой, что в нем ровно на k задач по математике больше, чем по экономике. Заметьте, что k может быть положительным, отрицательным или нулем.
К сожалению, Аня не уверена, на какой отрезок распространяется акция, но у нее есть q предположений. Для каждого из них она хочет заранее знать количество вариантов купить подотрезок, удовлетворяющий условию (ведь от этого зависит время, которое она потратит на выбор).
Сейчас Аня слишком занята решением других задач, поэтому просит вашей помощи. Определите для каждого предположения, сколько существует подотрезков данного отрезка таких, что задач по математике там ровно на k больше, чем по экономике.
Выходные данные
Выведите q строк, в i-й из которых количество подходящих подотрезков для i-го предположения Ани.
Примечание
В первом примере Ане подойдут подотрезки [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]
Примеры
| № | Входные данные | Выходные данные |
|
1
|
4 1
1 1 1 2
1 1 1 1
4
1 2
1 3
1 4
3 4
|
2
3
4
1
|
|
2
|
4 0
1 2 1 2
0 0 0 0
1
1 4
|
10
|