Matrice

Se consideră o matrice binară $A$ cu $K$ linii și $N$ coloane.

Cerință

Se dau $Q$ operații de următoarele două tipuri:

• $1\ i\ j$ – se inversează valoarea celulei $(i,j)$ (dacă este $0$ devine $1$ și invers).
• $2\ st\ dr$ – interogare prin care se cere să se determine lungimea minimă a unui drum valid care pornește din orice celulă a coloanei $st$ și se termină în orice celulă a coloanei $dr$, precum și numărul de astfel de drumuri de lungime minimă, calculat modulo $998244353$.

Un drum se consideră valid dacă include doar celule cu valoarea $0$, nu părăsește matricea, oricare două celule adiacente în drum au o latură comună, iar coloanele celulelor parcurse formează un șir monoton crescător. Lungimea unui drum este egală cu numărul de celule vizitate.

Formal: Drumul format din celulele $(i_1,j_1), (i_2,j_2), \dots, (i_x,j_x)$ (parcurse în această ordine) este valid dacă și numai dacă $A_{i_1,j_1} = A_{i_2,j_2} = \dots = A_{i_x,j_x} = 0$, $|i_k - i_{k-1}| + |j_k - j_{k-1}| = 1$ pentru orice $2 \le k \le x$, și $j_1 \le j_2 \le \dots \le j_x$.

Date de intrare

Prima linie conține două numere naturale, $K$ și $N$.
Pe următoarele $K$ linii se află câte un șir de $N$ valori din mulțimea $\{0, 1\}$, reprezentând matricea inițială.
Pe următoarea linie se află numărul natural $Q$.
Pe următoarele $Q$ linii se află câte trei numere naturale, reprezentând tipul operației ($1$ sau $2$) și parametrii acesteia.

Date de ieșire

Fișierul de ieșire va conține răspunsurile pentru operațiile de tipul $2$, câte unul pe rând. Fiecare răspuns va consta în două numere separate printr-un spațiu: lungimea minimă a drumului și numărul de drumuri de lungime minimă (modulo $998244353$).

Dacă nu există niciun astfel de drum valid, pe linia respectivă se va afișa -1 0.

Restricții și precizări

• $1 \le N, Q \le 50\ 000$
• $1 \le K \le 7$
• Pentru operațiile de tip $1$: $1 \le i \le K$ și $1 \le j \le N$.
• Pentru operațiile de tip $2$: $1 \le st \le dr \le N$.

Exemplu

matrice.in

3 6
0 0 0 1 0 0
1 1 0 1 0 1
0 1 0 0 0 1
3
2 1 6
1 1 4
2 1 6

matrice.out

10 1
6 1

Explicație

Prima operație ne întreabă care este lungimea minimă a unui drum care pornește de pe prima coloană și se termină pe ultima. Acest drum unic este format din celulele $(1,1), (1,2), (1,3), (2,3), \dots, (1,6)$.

A doua operație transformă celula $(1,4)$ într-un $0$.

A treia operație ne întreabă lungimea minimă a unui drum care începe pe prima coloană și se termină pe ultima. De data aceasta, drumul este în linie dreaptă, are o lungime de $6$ și este, de asemenea, unic.