Решения: Республиканская олимпиада, Заключительный этап

Республиканская олимпиада по информатике 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

Ответ

Замечание

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$

посмотреть в олимпиаде

Комментарий/решение: