== include(page="template/taskheader" task_id="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.
Poveste și cerință...
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, $l1, c1, l2, c2$, reprezetand coordonatele stanga-sus si respectiv dreapta-jos a dreptunghiului chestionat.
Fișierul de intrare $paint.in$ ...
h2. 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.
În fișierul de ieșire $paint.out$ ...
h2. 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$
* $... ≤ ... ≤ ...$
h2. Exemplu
table(example).
|_. paint.in |_. paint.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
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
|
h3. Explicație
...
== include(page="template/taskfooter" task_id="paint") ==
== include(page="template/taskfooter" task_id="paint") ==
