$$ \newcommand{\floor}[1]{\left\lfloor{#1}\right\rfloor} \newcommand{\ceil}[1]{\left\lceil{#1}\right\rceil} \renewcommand{\mod}{\,\mathrm{mod}\,} \renewcommand{\div}{\,\mathrm{div}\,} \newcommand{\metar}{\,\mathrm{m}} \newcommand{\cm}{\,\mathrm{cm}} \newcommand{\dm}{\,\mathrm{dm}} \newcommand{\litar}{\,\mathrm{l}} \newcommand{\km}{\,\mathrm{km}} \newcommand{\s}{\,\mathrm{s}} \newcommand{\h}{\,\mathrm{h}} \newcommand{\minut}{\,\mathrm{min}} \newcommand{\kmh}{\,\mathrm{\frac{km}{h}}} \newcommand{\ms}{\,\mathrm{\frac{m}{s}}} \newcommand{\mss}{\,\mathrm{\frac{m}{s^2}}} \newcommand{\mmin}{\,\mathrm{\frac{m}{min}}} \newcommand{\smin}{\,\mathrm{\frac{s}{min}}} $$

Prijavi problem


Obeleži sve kategorije koje odgovaraju problemu

Još detalja - opišite nam problem


Uspešno ste prijavili problem!
Status problema i sve dodatne informacije možete pratiti klikom na link.
Nažalost nismo trenutno u mogućnosti da obradimo vaš zahtev.
Molimo vas da pokušate kasnije.

Velika Matrica

vreme memorija ulaz izlaz
2 s 64 Mb standardni izlaz standardni ulaz

Prošlo je vreme igre, uživanja i razonode. Prošlo je vreme malih matrica. Danas su računari neverovatno brzi i mogu izvršiti i do komandi u sekundi. Iz tog razloga komisija vam je spremila jednostavan zadatak sa jednom matricom i mnogo interesantnih upita.

U ovom zadatku vam je data matrica dimenzije - matrica ima tačno vrsta i tačno kolona. Za svako () i () vrednost na poziciji () u matrici je definisano na sledeći način :

= ( + ) mod

Operacija predstavlja ostatak koji daje broj pri deljenju sa .

Potrebno je odgovoriti na upita oblika : Naći sumu svih brojeva u podmatrici matrice A sa gornjim levim temenom () i donjim desnim temenom() po modulu . Podmatrica matrice A sa navedenim ograničenjima obuhvata sve elemente takve da važi , .

Opis ulaza

U prvoj liniji standardnog ulaza nalaze se brojevi , , -- broj vrsta matrice , broj kolona matrice i modul opisan u tekstu zadatka, redom. Druga linija standardnog ulaza sadrži broj , broj upita na koje je potrebno odgovoriti. Narednih linija sadrže po četiri broja, koji predstaljaju, redom, vrstu gornjeg levog temena podmatrice, kolonu gornjeg levog temena podmatrice, vrstu donjeg desnog temena podmatrice i kolonu donjeg desnog temena podmatrice.

Opis izlaza

Na standardnom izlazu u redova odgovoriti na upite opisane u tekstu zadatka, tačnije u -toj liniji standardnog izlaza ispisati sumu tražene podmatrice po modulu iz -tog upita.

Primer

Ulaz

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

Izlaz

7
6
0

Objašnjenje primera

Matrica je dimenzija , . Matrica izgleda:

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

U prvom upitu, gornje levo teme podmatrice ima koordinate (), dok donje desno teme ima koordinate (). Rešenje ovog upita je: = = .

U trećem upitu jedini broj se nalazi na polju () i on ima vrednost . Rešenje ovog upita je .

Ograničenja

Podzadaci

Test primeri su podeljeni u pet disjunktnih grupa:

  • U primerima vrednim 10 poena važiće ograničenje
  • U primerima vrednim 10 poena važiće ograničenje
  • U primerima vrednim 10 poena važiće ograničenje
  • U primerima vrednim 30 poena važiće ograničenje ,
  • U primerima vrednim 40 poena nema dodatnih ograničenja.

Morate biti ulogovani kako biste poslali zadatak na evaluaciju.