Напомена: ово је незванична копија задатака. Као таква, не гарантује се да ће овај сајт бити одржаван, и немојте се изненадити ако са њега задаци одједном нестану.

Прошло је време игре, уживања и разоноде. Прошло је време малих матрица. Данас су рачунари невероватно брзи и могу извршити и до \(10^{100}\) команди у секунди. Из тог разлога комисија вам је спремила једноставан задатак са једном матрицом и много интересантних упита.

У овом задатку вам је дата матрица димензије \(n \cdot m\) - матрица има тачно \(n\) врста и тачно \(m\) колона. За свако \(i\) (\(1 \leq i \leq n\)) и \(j\) (\(1 \leq j \leq m\)) вредност на позицији (\(i,j\)) у матрици \(A\) је дефинисано на следећи начин :

\(А_{i,j}\) = (\(i\) + \(j\)) mod \(M\)

Операција \(X\) \(mod\) \(M\) представља остатак који даје број \(X\) при дељењу са \(M\).

Потребно је одговорити на \(q\) упита облика : Наћи суму свих бројева у подматрици матрице А са горњим левим теменом (\(x_l,y_l\)) и доњим десним теменом(\(x_r,y_r\)) по модулу \(10^9+7\). Подматрица матрице А са наведеним ограничењима обухвата све елементе \(A_{i,j}\) такве да важи \(x_l \leq i \leq x_r\) , \(y_l \leq j \leq y_r\).

Опис улаза

У првој линији стандардног улаза налазе се бројеви \(n\), \(m\), \(M\) – број врста матрице \(A\), број колона матрице \(A\) и модул \(M\) описан у тексту задатка, редом. Друга линија стандардног улаза садржи број \(q\), број упита на које је потребно одговорити. Наредних \(q\) линија садрже по четири броја, који предстаљају, редом, врсту горњег левог темена подматрице, колону горњег левог темена подматрице, врсту доњег десног темена подматрице и колону доњег десног темена подматрице.

Опис излаза

На стандардном излазу у \(q\) редова одговорити на упите описане у тексту задатка, тачније у \(i\)-тој линији стандардног излаза исписати суму тражене подматрице по модулу \(10^9+7\) из \(i\)-тог упита.

Пример

Улаз

5 4 3
3
1 2 4 3
2 3 4 4
3 3 3 3

Излаз

7
6
0

Објашњење примера

Матрица је димензија \(5 \cdot 4\), \(M=3\). Матрица изгледа:

                2 0 1 2
                0 1 2 0
                1 2 0 1
                2 0 1 2
                0 1 2 0

У првом упиту, горње лево теме подматрице има координате (\(1,2\)), док доње десно теме има координате (\(4,3\)). Решење овог упита је: $ (0 + 1 + 1 +2 +2 + 0 + 0 +1 )    10^9+7 $ = \(7 \ \text{ mod } \ 10^9+7\) = \(7\).

У трећем упиту једини број се налази на пољу (\(3,3\)) и он има вредност \(0\). Решење овог упита је $ 0    10^9+7 = 0$.

Ограничења

\(1 \leq n,m,M \leq 10^9\)

\(1 \leq q \leq 2\cdot 10^5\)

Подзадаци

Тест примери су подељени у пет дисјунктних група: