eolymp
bolt
Попробуйте наш новый интерфейс для отправки задач
Задачи

Сумма в симпатичной таблице

Сумма в симпатичной таблице

Лимит времени 1 секунда
Лимит использования памяти 122 MiB

Вам задана прямоугольная таблица 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, ответом на каждый запрос будет сумма чисел в соответствующем подпрямоугольнике по соответствующему модулю.

Более формально

prb7839.gif

Напишите программу, отвечающую на заданные запросы.

Симпатичная таблица A, 3 на 4, для числа x будет выглядеть следующим образом:

prb7839_1.gif

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

В первой строке заданы три целых числа n, m, x (1n, m, x10^9). В следующей строке задано единственное целое число q (1q10^4). В следующих q строках заданы запросы, каждый запрос задается пятью числами x1, x2, y1, y2, p (1x1x2n, 1y1y2m, 1p10^9).

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

Выведите q чисел, по одному на каждой строке, ответы на соответствующие запросы.

Пример

Входные данные #1
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
Выходные данные #1
2
6
62
28
12
Источник 2014 Казахстан, 4-й этап Республиканской олимпиады по информатике, Усть-Каменогорск, Март, Задача E