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

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

Ограничение по времени Ограничение по памяти
1 секунда 64 мегабайта

Вам задана прямоугольная таблица AA из nn строк и mm столбцов. В этой таблице ровно n×mn \times m ячеек, пронумерованных последовательно натуральными числами сверху вниз, слева направо. A[i][j]A[i][j] будем обозначать ячейку прямоугольной таблицы AA стоящей на пересечений ii-ой строки и jj-го столбца. Для конкретно заданного числа xx симпатичной таблицей будет являться таблица AA, для которой значения в ячейках таблицы будут равны xx в степени номера соответствующей ячейки. Более формально A[i][j]=x(i1)m+jA[i][j] = x^{(i - 1) * m + j}.

Даны qq запросов границы под прямоугольника x1,x2,y1,y2x1,x2,y1,y2 и модуль pp, ответом на каждый запрос будет сумма чисел в соответствующем под прямоугольнике по соответствующему модулю.

Более формально (i=x1x2j=y1y2A[i][j])mod p\left(\sum\limits_{i=x1}^{x2}{\sum\limits_{j=y1}^{y2}{A[i][j]}}\right) mod\ p. Напишите программу, отвечающую на заданные запросы.

Симпатичная таблица AA, 33 на 44, для числа xx будет выглядеть следующим образом:\ A=(x1x2x3x4x5x6x7x8x9x10x11x12)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,xn,m,x. В следующей строке входных данных задано единственное целое число qq. В следующих qq строках входных данных заданы запросы, каждый запрос задается пятью числами, разделенных пробелами x1,x2,y1,y2,px1,x2,y1,y2,p, 1x1x2n1 \le x1 \le x2 \le n, 1y1y2m1 \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