Fişierul intrare/ieşire:paint.in, paint.outSursăOlimpiada pe Scoala 2012, Clasa a 7-a
AutorTeodor PlopAdăugată deteodor94Teodor Plop teodor94
Timp execuţie pe test0.6 secLimită de memorie16384 kbytes
Scorul tăuN/ADificultatenormalnormalnormalnormalnormal

Vezi solutiile trimise

Paint

Recent, Gigel doreste sa isi etaleze abilitatile sale de zidar profesionist.

Acesta are de colorat un perete, codificat sub forma unei matrice cu N linii si M coloane formata din elemente 0 si 1 astfel: 0 reprezinta un patrat colorabil, iar 1 reprezinta un patrat incolorabil.

Gigel are la dispozitie 2 culori diferite pentru a colora aceste patratele. Se stie ca orice patratel colorabil poate si trebuie sa fie colorat intr-o singura culoare (aceasta implica faptul ca orice patratel colorabil trebuie colorat, nu trebuie lasat mat).

Lui Gigel ii sunt puse Q intrebari de genul: "In cate moduri distincte poate fi colorat dreptunghiul avand coltul din stanga sus in (l1, c1) si coltul din dreapta jos in (l2, c2)?".

Cunoscandu-se N, M si matricea reprezentand peretele ce trebuie colorat, sa se raspunda la cele Q intrebari ale lui Gigel! Raspunsurile fiind numere foarte mari, se cere rezultatul acestora modulo 1001.

Date de intrare

Fişierul de intrare paint.in va contine pe prima linie 2 numere naturale N si M. Pe urmatoarele N linii vor fi scrise M valori (0 sau 1) separate prin cate un spatiu, reprezentand codificarea peretelui. Pe linia N + 2 se va afla numarul natural Q, numarul de intrebari la care va trebui sa raspundeti. Pe urmatoarele Q linii se vor afla cate 4 numere naturale separate prin cate un spatiu, l1, c1, l2, c2, reprezetand coordonatele stanga-sus si respectiv dreapta-jos a dreptunghiului chestionat.

Date de ieşire

În fişierul de ieşire paint.out se vor afla exact Q linii, pe fiecare linie i aflandu-se raspunsul la intrebarea i pusa lui Gigel.

Restricţii

  • 1 ≤ N, M ≤ 1000
  • 1 ≤ Q ≤ 100000
  • 1 ≤ l1 ≤ l2 ≤ N
  • 1 ≤ c1 ≤ c2 ≤ M
  • Pentru 60 de puncte 1 ≤ N ≤ 100 si 1 ≤ Q ≤ 100

Exemplu

paint.inpaint.out
3 4
0 1 0 1
0 0 0 1
1 0 1 0
2
1 2 3 2
1 4 2 4
4
1
Trebuie sa te autentifici pentru a trimite solutii. Click aici