Loterie

Cel mai bun prieten al tău, Andrei a reușit să afle informații despre matricea corespunzătoare numerelor din următoarea loterie. El știe că matricea este de $N$ rânduri și $M$ coloane. Mai mult, $a[1][1]=1$ și $a[i][j]=a[i-1][j]+1$ pentru $i\neq1$, $a[i][j]=a[n][j-1]+1$, pentru $i=1$, $j\neq1$. Totuși, nu este suficient pentru a câștiga. Acum el trebuie să descifreze răspunusul la $Q$ întrebări. Mai întâi, pentru premiul secundar, trebuie să răspundă la $Q$ întrebări de forma: Ce element se află pe poziția $(i,j)$ în matrice? Apoi, pentru premiul cel mare, întrebările se complică și sunt de forma: Care este suma elementelor din submatricea cu colțul stânga sus $(i,j)$ și cel dreapta jos $(k,l)$, modulo $10^9+7$?

Cerință

• Determinați răspunsul la întrebările pentru premiul secundar.
• Determinați răspunsul la întrebările pentru premiul cel mare.

Date de intrare

Pe prima linie a fișierului de intrare loterie.in se găsesc patru numere întregi, $C$, $N$, $M$, $Q$, reprezentând cerința, numărul de linii și coloane ale matricei și numărul de întrebări. Dacă $C=1$, pe următoarele $Q$ linii se găsesc două numere naturale cu semnificația din enunț. Dacă $C=2$, pe următoarele $Q$ linii se găsesc patru numere naturale cu semnificația din enunț.

Date de ieșire

În fișierului de ieșire loterie.out se vor găsi $Q$ numere, pe linii diferite, pe linia $i$ găsindu-se răspunsul la întrebarea $i$.

Restricții și precizări

• $1 \leq N, M \leq 1 \ 000 \ 000$;
• $1 \leq Q \leq 50 \ 000$;
• Fie $(i,j)$ o întrebare pentru $C=1$, atunci $1 \leq i\leq N$ și $1 \leq j\leq M$
• Fie $(i,j,k,l)$ o întrebare pentru $C=2$, atunci $1 \leq i \leq k \leq N$ și $1 \leq j \leq l \leq M$
• Pentru $C=2$, suma numerelor se afișează modulo $10^9+7$
• Matricea este indexată de la $1$

  #	Punctaj	Restricții
  1	15	$C=1, 1 \leq N,M \leq 5 \ 000$
  2	25	$C=1$
  3	10	$C=2, 1\leq N,M \leq 5 \ 000$ , $Q=1$
  4	10	$C=2, 1\leq N,M \leq 5 \ 000$
  5	40	$C=2$

Exemplul 1

loterie.in

1 4 5 3
2 3
4 5
1 4

loterie.out

10
20
13

Explicație

Matricea arată astfel:

Exemplul 2

loterie.in

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

loterie.out

135 
210
63

Explicație

Suma elementelor din subamtricea cu colțul stânga sus în $(2,3)$ și cel dreapta jos $(4,5)$ este
$(10+14+18+11+15+19+12+16+20)$%$(10^9+7)=135$