== include(page="template/taskheader" task_id="paint") ==
Recent, Gigel doreste sa isi etaleze abilitatile sale de zidar.
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 (0 reprezinta un patrat colorabil, iar 1 reprezinta un patrat incolorabil).
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).
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 (x1, y1) si coltul din dreapta jos in (x2, y2)?".
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!
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.
h2. 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, $x1, y1, x2, y2$, reprezetand coordonatele stanga-sus si respectiv dreapta-jos a dreptunghiului chestionat.
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.
h2. Date de ieșire
h2. Restricții
* $1 ≤ [$N$], $M$ ≤ 100$
* $1 ≤ $Q$ ≤ 10000$
* $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$
h2. Exemplu
table(example).
|_. paint.in |_. paint.out |
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
| 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
|
h3. Explicație
...
== include(page="template/taskfooter" task_id="paint") ==
