La part de hasard est omniprésente et imprègne toute l'existence. Même dans les compétitions les plus cruciales, le facteur décisif peut souvent n'être que de la chance.

En 2035, $n$ passionnés du jeu « Clash Royale » souhaitent comparer leurs niveaux. Pour plus d'équité, ils décident de s'affronter tous deux par deux, pour un total de $\frac{n(n-1)}{2}$ matchs.

Cependant, à cette époque, « Clash Royale » a complètement évolué en un jeu de « Pierre-Papier-Ciseaux » ! Par conséquent, dans chaque match, la probabilité que l'un ou l'autre des joueurs gagne est de 50 %, et les résultats sont indépendants.

Les joueurs vaincus ne sont naturellement pas satisfaits. Pour obtenir une « victoire spirituelle », ils introduisent le concept de « victoire indirecte » : On définit que $u$ remporte une $k$-victoire indirecte sur $v$ si et seulement s'il existe $k$ personnes $a_1, \dots, a_k$ telles que $u$ a battu $a_1$, $a_1$ a battu $a_2$, $a_i$ a battu $a_{i+1}$ ($\forall i \in [1, k)$), et $a_k$ a battu $v$.

En particulier, si $u$ a battu directement $v$, on appelle cela une 0-victoire indirecte.

Les joueurs se posent alors une nouvelle question : étant donné deux joueurs $u$ et $v$, quel est le nombre minimal de niveaux de relations indirectes nécessaires pour dire que $u$ a battu $v$ ?

En d'autres termes, vous devez trouver le plus petit entier $k$ tel que $u$ puisse remporter une $k$-victoire indirecte sur $v$. Comme il y a beaucoup de joueurs insatisfaits, vous devez répondre à $q$ requêtes.

Entrée

Veuillez noter : le volume d'entrées/sorties de ce problème est important. Il est conseillé d'utiliser des méthodes de lecture et d'écriture rapides, par exemple scanf/printf en C++ ou cin/cout avec la synchronisation désactivée. Il est recommandé d'éviter les langages dont les entrées/sorties sont lentes.

La première ligne contient deux entiers $n, q$ ($2 \le n \le 5000, 1 \le q \le 10^5$).

Les $n-1$ lignes suivantes : la $i$-ième ligne est une chaîne binaire de longueur $n-i$, où le $j$-ième chiffre ($1 \le j \le n-i$) est $1$ si la $i$-ième personne a battu la $(i+j)$-ième personne, sinon cela signifie que la $(i+j)$-ième personne a battu la $i$-ième personne. Il est garanti que les relations de victoire/défaite sont générées de manière aléatoire et indépendante, avec une probabilité de 50 %.

Les $q$ lignes suivantes : la $i$-ième ligne contient deux entiers $u_i, v_i$ ($1 \le u_i, v_i \le n, u_i \neq v_i$) représentant la $i$-ième requête.

Sortie

Affichez $q$ lignes, où la $i$-ième ligne contient un entier $k$ représentant le plus petit $k$ tel que $u_i$ remporte une $k$-victoire indirecte sur $v_i$. En particulier, si pour tout $k$, $u_i$ ne peut pas remporter une $k$-victoire indirecte sur $v_i$, affichez $-1$.

Exemples

Entrée 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

Sortie 1

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

Entrée 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

Sortie 2

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