Республиканская олимпиада по информатике 2014 год, Усть-Каменогорск

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

Ограничение по времени:

1 секунда

Ограничение по памяти:

64 мегабайта

Вам задана прямоугольная таблица $A$ из $n$ строк и $m$ столбцов. В этой таблице ровно $n \times m$ ячеек, пронумерованных последовательно натуральными числами сверху вниз, слева направо. $A[i][j]$ будем обозначать ячейку прямоугольной таблицы $A$ стоящей на пересечений $i$-ой строки и $j$-го столбца. Для конкретно заданного числа $x$ симпатичной таблицей будет являться таблица $A$, для которой значения в ячейках таблицы будут равны $x$ в степени номера соответствующей ячейки. Более формально $A[i][j] = x^{(i - 1) * m + j}$. Даны $q$ запросов границы под прямоугольника $x1,x2,y1,y2$ и модуль $p$, ответом на каждый запрос будет сумма чисел в соответствующем под прямоугольнике по соответствующему модулю. Более формально $\left(\sum\limits_{i=x1}^{x2}{\sum\limits_{j=y1}^{y2}{A[i][j]}}\right) mod\ p$. Напишите программу, отвечающую на заданные запросы. Симпатичная таблица $A$, $3$ на $4$, для числа $x$ будет выглядеть следующим образом:\\ $A = \begin{pmatrix} x^{1} & x^{2} & x^{3} & x^{4}\\ x^{5} & x^{6} & x^{7} & x^{8}\\ x^{9} & x^{10} & x^{11} & x^{12} \end{pmatrix}$

Формат входного файла

В первой строке входных данных заданы три целых числа, разделенных пробелами $n,m,x$. В следующей строке входных данных задано единственное целое число $q$. В следующих $q$ строках входных данных заданы запросы, каждый запрос задается пятью числами, разделенных пробелами $x1,x2,y1,y2,p$, $1 \le x1 \le x2 \le n$, $1 \le y1 \le y2 \le m$.

Формат выходного файла

Выведите 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

Замечание

Подзадача 1 — 7 баллов $n = 1$, $1 \le m \le 10$, $1 \le x \le 5$, $1 \le q \le 100$, $p = 10^9 + 7$ Подзадача 2 — 9 баллов $1 \le n \le 100$, $1 \le m \le 100$, $1 \le x \le 10^9$, $1 \le q \le 100$, $p = 10^9 + 7$ Подзадача 3 — 11 баллов $1 \le n \le 1000$, $1 \le m \le 1000$, $1 \le x \le 10^9$, $1 \le q \le 10^4$, $p = 10^9 + 7$ Подзадача 4 — 21 баллов $1 \le n \le 10^9$, $1 \le m \le 10^9$, $1 \le x \le 10^9$, $1 \le q \le 10^4$, $p = 10^9 + 7$ Подзадача 5 — 52 баллов $1 \le n \le 10^9$, $1 \le m \le 10^9$, $1 \le x \le 10^9$, $1 \le q \le 10^4$, $1 \le p \le 10^9$