bila

Într-un laborator experimental, cercetătorii testează comportamentul unei bile într-un mediu discret, reprezentat sub forma unei matrici. Fiecare celulă a matricii poate reprezenta fie pământ, fie aer, iar bila se deplasează conform unor reguli bine stabilite. Mediul este reprezentat printr-o matrice cu $N$ linii și $M$ coloane, alcătuită doar din valori $0$ și $1$: $1$ reprezintă o zonă cu pământ, iar $0$ reprezintă o zonă cu aer. Cercetătorii pot da drumul unei bile dintr-o anumită celulă cu aer a matricii. Odată eliberată, bila se deplasează repetat conform următoarelor reguli: dacă celula de sub bilă este în interiorul matricei și conține aer, bila cade în jos. Altfel, dacă celula de sub bilă este pământ sau se află în afara matricei, bila încearcă să se deplaseze spre dreapta. Dacă și celula din dreapta conține pământ, bila se blochează și nu mai poate continua. Bila iese din matrice atunci când ajunge pe o poziție din care următoarea mutare o scoate în afara limitelor matricei.

Cerință

Se dă un număr $C$ care indică cerința ce trebuie rezolvată:

• Dacă $C=1$, determinați numărul total de celule cu pământ din matrice.
• Dacă $C=2$, determinați pentru o poziție dată $(i,j)$, dacă bila care pornește de la acea poziție poate ieși din matrice fără să se blocheze.
• Dacă $C=3$, determinați pentru mai multe poziții $(i,j)$, distanța până la ieșirea din matrice a bilei ce pornește din acea poziție. Dacă bila se blochează pe parcurs, se va afișa $-1$.

Date de intrare

Pe prima linie a fișierului de intrare bila.in se află trei numere naturale: $C$, $N$, $M$. Pe următoarele $N$ linii se află câte $M$ valori ($0$ sau $1$) separate prin câte un spațiu.

• Dacă $C=2$, pe următoarea linie se află două numere naturale $i$ și $j$, poziția de start a bilei.
• Dacă $C=3$, pe următoarea linie se află un număr natural $Q$, reprezentând numărul de interogări, iar pe următoarele $Q$ linii se află câte două numere naturale $i$ și $j$.

Date de ieșire

În fișierul de ieșire bila.out se va găsi răspunsul în funcție de cerință după cum urmează:

• Dacă $C = 1$, se va afișa pe prima linie un singur număr: numărul total de celule cu pământ.
• Dacă $C = 2$, se va afișa pe prima linie un singur număr: $1$, dacă bila poate ieși din matrice, iar $0$ în caz contrar.
• Dacă $C = 3$, se vor afișa $Q$ numere, câte unul pe fiecare linie. Numărul de pe linia $i$ va reprezenta distanța parcursă de bila $i$ sau $-1$, dacă bila se blochează.

Restricții și precizări

• $1 \leq N, M \leq 3 \ 000$
• $1 \leq Q \leq 200 \ 000$
• Elementele din matrice sunt egale cu $0$ sau $1$

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

Exemplul 1

bila.in

1 5 6
0 0 0 0 0 0
0 1 0 1 0 0
0 1 1 1 1 0
0 0 0 0 0 1
1 1 1 1 0 0

bila.out

11

Exemplul 2

bila.in

2 5 6
0 0 0 0 0 0
0 1 0 1 0 0
0 1 1 1 1 0
0 0 0 0 0 1
1 1 1 1 0 0
1 2

bila.out

0

Exemplul 3

bila.in

3 5 6
0 0 0 0 0 0
0 1 0 1 0 0
0 1 1 1 1 0
0 0 0 0 0 1
1 1 1 1 0 0
4
5 6
1 1
1 3
1 4

bila.out

1
10
-1
5