Losowość jest wszechobecna i towarzyszy nam przez całe życie. Nawet w najważniejszych zawodach o zwycięstwie często decyduje po prostu szczęście.

W 2035 roku $n$ zagorzałych fanów gry "Clash Royale" chce sprawdzić, kto z nich jest lepszy. Dla sprawiedliwości postanowili rozegrać mecze każdy z każdym, co daje łącznie $\frac{n(n-1)}{2}$ spotkań.

Jednak w tamtym czasie "Clash Royale" całkowicie zmieniło się w "papier, kamień, nożyce"! Dlatego w każdym meczu prawdopodobieństwo wygranej obu stron wynosi 50% i jest od siebie niezależne.

Przegrani gracze naturalnie czują niedosyt. Aby osiągnąć "zwycięstwo duchowe", wprowadzili pojęcie "pośredniego zwycięstwa": Mówimy, że $u$ odnosi $k$-pośrednie zwycięstwo nad $v$ wtedy i tylko wtedy, gdy istnieje $k$ osób $a_1, \dots, a_k$ takich, że $u$ wygrał z $a_1$, $a_1$ wygrał z $a_2$, $a_i$ wygrał z $a_{i+1}$ (dla $i \in [1, k)$), a $a_k$ wygrał z $v$.

W szczególności, jeśli $u$ bezpośrednio wygrał z $v$, nazywamy to 0-pośrednim zwycięstwem.

Gracze zadali sobie nowe pytanie: mając dwóch graczy $u$ oraz $v$, ile minimalnie warstw pośrednich relacji potrzeba, aby stwierdzić, że $u$ wygrał z $v$?

Innymi słowy, musisz wyznaczyć minimalną liczbę całkowitą $k$, taką że $u$ może odnieść $k$-pośrednie zwycięstwo nad $v$. Ponieważ graczy czujących niedosyt jest wielu, musisz odpowiedzieć na $q$ zapytań.

Wejście

Uwaga: Wejście w tym zadaniu jest duże, zaleca się stosowanie szybkich metod wczytywania i wypisywania danych, np. w C++ użycie scanf/printf lub wyłączenie synchronizacji strumieni cin/cout. Zaleca się unikanie języków z wolnym wejściem/wyjściem.

Pierwsza linia zawiera dwie liczby całkowite $n, q$ ($2 \le n \le 5000, 1 \le q \le 10^5$).

Następnie $n-1$ linii, gdzie $i$-ta linia zawiera ciąg binarny o długości $n-i$. Jeśli $j$-ty ($1 \le j \le n-i$) znak to 1, oznacza to, że osoba $i$ wygrała z osobą $i+j$, w przeciwnym razie osoba $i+j$ wygrała z osobą $i$. Gwarantuje się, że relacje zwycięstwa są generowane niezależnie i losowo, z prawdopodobieństwem 50%.

Następnie $q$ linii, gdzie $i$-ta linia zawiera dwie liczby całkowite $u_i, v_i$ ($1 \le u_i, v_i \le n, u_i \neq v_i$), reprezentujące $i$-te zapytanie.

Wyjście

Wypisz $q$ linii. W $i$-tej linii wypisz jedną liczbę całkowitą $k$ oznaczającą minimalne $k$, dla którego $u_i$ odnosi $k$-pośrednie zwycięstwo nad $v_i$. W szczególności, jeśli dla żadnego $k$ gracz $u_i$ nie może odnieść $k$-pośredniego zwycięstwa nad $v_i$, wypisz -1.

Przykład

Wejście 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

Wyjście 1

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

Wejście 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

Wyjście 2

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