Сумма в симпатичной таблице
Вам задана прямоугольная таблица 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 ≤ 10^9). В следующей строке задано единственное целое число q (1 ≤ q ≤ 10^4). В следующих q строках заданы запросы, каждый запрос задается пятью числами x1, x2, y1, y2, p (1 ≤ x1 ≤ x2 ≤ n, 1 ≤ y1 ≤ y2 ≤ m, 1 ≤ p ≤ 10^9).
Выходные данные
Выведите q чисел, по одному на каждой строке, ответы на соответствующие запросы.