Республиканская олимпиада по информатике 2014 года за 9 класс | Казахстанские олимпиады

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

Вам задана прямоугольная таблица $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