La aleatoriedad está en todas partes y acompaña a la vida desde el principio. Incluso en las competiciones más importantes, la clave que decide la victoria o la derrota a menudo puede ser simplemente la suerte.

En el año 2035, $n$ entusiastas del juego "Clash Royale" quieren comparar quién tiene un mayor nivel. Para ser justos, deciden enfrentarse todos contra todos, realizando un total de $\frac{n(n-1)}{2}$ partidas.

Sin embargo, en aquel entonces, "Clash Royale" se había convertido por completo en "piedra, papel o tijera". Por lo tanto, en cada partida, la probabilidad de que cualquiera de los dos jugadores gane es del 50%, y los resultados son independientes entre sí.

Los jugadores que pierden, naturalmente, no se quedan conformes. Para obtener una "victoria espiritual", introducen el concepto de "victoria indirecta": Se define que $u$ tiene una $k$-victoria indirecta sobre $v$ si y solo si existen $k$ personas $a_1, \dots, a_k$ tales que $u$ venció a $a_1$, $a_1$ venció a $a_2$, $a_i$ venció a $a_{i+1}$ ($\forall i \in [1, k)$), y $a_k$ venció a $v$.

En particular, si $u$ venció directamente a $v$, se denomina 0-victoria indirecta.

Los jugadores se plantean entonces una nueva duda: dados dos jugadores $u$ y $v$, ¿cuántas capas de relaciones indirectas se necesitan como mínimo para decir que $u$ venció a $v$?

En otras palabras, debes encontrar el entero mínimo $k$ tal que $u$ pueda obtener una $k$-victoria indirecta sobre $v$. Como hay muchos jugadores insatisfechos, debes responder a $q$ consultas.

Entrada

Ten en cuenta: el volumen de entrada/salida de este problema es grande, se recomienda utilizar métodos de lectura y escritura rápidos, por ejemplo, scanf/printf en C++ o cin/cout con la sincronización desactivada. Se recomienda evitar lenguajes con entrada y salida lentas.

La primera línea contiene dos enteros $n, q$ ($2 \le n \le 5000, 1 \le q \le 10^5$).

Las siguientes $n-1$ líneas, la línea $i$ es una cadena binaria de longitud $n-i$, donde el $j$-ésimo ($1 \le j \le n-i$) dígito es 1 si la persona $i$ venció a la persona $i+j$, de lo contrario, significa que la persona $i+j$ venció a la persona $i$. Se garantiza que las relaciones de victoria/derrota se generan de forma aleatoria e independiente, con una probabilidad del 50% cada una.

Las siguientes $q$ líneas, la línea $i$ contiene dos enteros $u_i, v_i$ ($1 \le u_i, v_i \le n, u_i \neq v_i$) que representan la $i$-ésima consulta.

Salida

Imprime $q$ líneas, donde la línea $i$ contiene un entero $k$ que representa el $k$ mínimo tal que $u_i$ tiene una $k$-victoria indirecta sobre $v_i$. En particular, si para cualquier $k$, $u_i$ no puede obtener una $k$-victoria indirecta sobre $v_i$, imprime -1.

Ejemplos

Entrada 1

4 12
110
11
1
1 2
1 3
1 4
2 1
2 3
2 4
3 1
3 2
3 4
4 1
4 2
4 3

Salida 1

0
0
1
1
0
0
1
2
0
0
1
1

Entrada 2

5 20
0011
001
01
1
1 2
1 3
1 4
1 5
2 1
2 3
2 4
2 5
3 1
3 2
3 4
3 5
4 1
4 2
4 3
4 5
5 1
5 2
5 3
5 4

Salida 2

1
1
0
0
0
2
1
0
0
0
1
0
1
0
0
0
-1
-1
-1
-1