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

(Әдемі кестедегі қосынды)

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

1 секунд

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

64 мегабайт

Сізге $n$ жолдан және $m$ қатардан тұратын кесте $A$ берілген. Бұл кестенің $n \times m$ торлары натуралды сандармен жоғарыдан төменге, солдан оңға қарай белгіленген. $A[i][j]$ деп $i$-жолында және $j$-қатарында тұрған торды белгілейміз. Берілген $x$ саны үшін біздің кесте әдемі болады, егер әр торда $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$. Сұрауларға жауап беретін программа жазыңыз. $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$