Селекционер ведёт учёт масс образцов, поступающих на ленту сбора. Для этого он записал последовательность из n целых положительных чисел a_1, a_2, ..., a_n, где a_i — масса образца на позиции i.

Также задано эталонное число D. Образец считается подходящим для текущего этапа анализа, если его масса кратна D.

Необходимо обработать q запросов. В каждом запросе заданы границы l и r выделенного диапазона ленты сбора. Для этого диапазона нужно найти суммарную массу всех образцов с позиций от l до r, чьи массы кратны D.

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

Первая строка содержит три целых числа n, q, D — количество образцов, количество запросов и эталонное число.

Вторая строка содержит n целых чисел a_i — массы образцов.

В следующих q строках содержится по два целых числа l и r — границы диапазона ленты сбора.

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

Для каждого запроса выведите в отдельной строке одно целое число — сумму масс образцов на отрезке [l, r], которые кратны D.

Ограничения

• 1 <= n, q <= 2 * 10^5
• 1 <= D <= 10^9
• 1 <= a_i <= 10^9
• 1 <= l <= r <= n

Примеры

Пример 1

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

5 6 3
1 3 6 7 9
1 1
1 3
2 5
4 5
3 3
1 5

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

0
9
18
9
6
18

Пример 2

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

8 8 1
5 1 2 8 3 13 21 34
1 8
1 1
8 8
2 7
3 5
4 4
5 8
2 2

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

87
5
34
48
13
8
71
1