Случайность повсюду, она пронизывает всю нашу жизнь. Даже в самых важных соревнованиях исход часто может зависеть лишь от удачи.

В 2035 году $n$ фанатов игры «Clash Royale» решили выяснить, кто из них играет лучше. Чтобы всё было честно, они решили сыграть друг с другом, проведя в общей сложности $\frac{n(n-1)}{2}$ матчей.

Однако к тому времени «Clash Royale» окончательно превратилась в «Камень, ножницы, бумага»! Поэтому в каждом матче вероятность победы любого из игроков составляет 50%, и результаты матчей независимы.

Проигравшие игроки, естественно, остались недовольны. Чтобы получить «моральное удовлетворение», они ввели понятие «косвенной победы»: Будем говорить, что $u$ одержал $k$-косвенную победу над $v$, если и только если существуют $k$ человек $a_1, \dots, a_k$ таких, что $u$ победил $a_1$, $a_1$ победил $a_2$, $a_i$ победил $a_{i+1}$ (для всех $i \in [1, k)$), а $a_k$ победил $v$.

В частности, если $u$ напрямую победил $v$, это называется 0-косвенной победой.

У игроков возник новый вопрос: при заданных двух игроках $u$ и $v$, какое минимальное количество промежуточных звеньев необходимо, чтобы сказать, что $u$ победил $v$?

Иными словами, вам нужно найти минимальное целое число $k$, такое что $u$ может одержать $k$-косвенную победу над $v$. Поскольку недовольных игроков очень много, вам нужно ответить на $q$ запросов.

Входные данные

Пожалуйста, обратите внимание: объем входных данных в этой задаче велик, рекомендуется использовать быстрые способы ввода и вывода, например, scanf/printf в C++ или cin/cout с отключенной синхронизацией. Рекомендуется избегать использования медленных языков программирования.

Первая строка содержит два целых числа $n, q$ ($2 \le n \le 5000, 1 \le q \le 10^5$).

Далее следуют $n-1$ строк. В $i$-й строке содержится бинарная строка длины $n-i$, где $j$-й ($1 \le j \le n-i$) символ равен 1, если $i$-й игрок победил $(i+j)$-го игрока, иначе $j$-й символ равен 0, что означает, что $(i+j)$-й игрок победил $i$-го игрока. Гарантируется, что результаты матчей сгенерированы случайно и независимо с вероятностью 50%.

Далее следуют $q$ строк, в $i$-й строке содержатся два целых числа $u_i, v_i$ ($1 \le u_i, v_i \le n, u_i \neq v_i$), представляющие $i$-й запрос.

Выходные данные

Выведите $q$ строк. В $i$-й строке выведите целое число $k$ — минимальное значение $k$, при котором $u_i$ одержал $k$-косвенную победу над $v_i$. В частности, если для любого $k$ игрок $u_i$ не может одержать $k$-косвенную победу над $v_i$, выведите -1.

Примеры

Примеры 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

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

Примеры 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

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