Сумма в симпатичной таблице
Сумма в симпатичной таблице
Вам задана прямоугольная таблица A из n строк и m столбцов. В этой таблице ровно n × m ячеек, пронумерованных последовательно натуральными числами сверху вниз, слева направо. A[i][j] будем обозначать ячейку прямоугольной таблицы A стоящей на пересечений i-ой строки и j-го столбца. Для конкретно заданного числа x симпатичной таблицей будет являться таблица A, для которой значения в ячейках таблицы будут равны x в степени номера соответствующей ячейки. Более формально A[i][j] = x{i−1}∗m+j
.
Даны q запросов границы подпрямоугольника x1, x2, y1, y2 и модуль p, ответом на каждый запрос будет сумма чисел в соответствующем подпрямоугольнике по соответствующему модулю.
Более формально
Напишите программу, отвечающую на заданные запросы.
Симпатичная таблица A, 3 на 4, для числа x будет выглядеть следующим образом:
Входные данные
В первой строке заданы три целых числа n, m, x (1 ≤ n, m, x ≤ 109
). В следующей строке задано единственное целое число q (1 ≤ q ≤ 104
). В следующих q строках заданы запросы, каждый запрос задается пятью числами x1, x2, y1, y2, p (1 ≤ x1 ≤ x2 ≤ n, 1 ≤ y1 ≤ y2 ≤ m, 1 ≤ p ≤ 109
).
Выходные данные
Выведите q чисел, по одному на каждой строке, ответы на соответствующие запросы.
1 10 2 5 1 1 1 1 1000000007 1 1 1 2 1000000007 1 1 1 5 1000000007 1 1 2 4 1000000007 1 1 2 3 1000000007
2 6 62 28 12