무작위성은 어디에나 존재하며 인생의 시작부터 끝까지 함께합니다. 매우 중요한 경기에서조차 승패를 결정짓는 핵심 요소는 운일 때가 많습니다.

2035년, $n$명의 《클래시 로얄》 게임 열성 팬들이 누가 더 실력이 뛰어난지 비교하고 싶어 합니다. 공정함을 위해 그들은 서로 한 번씩 대결하기로 했고, 총 $\frac{n(n-1)}{2}$번의 경기를 치렀습니다.

하지만 당시의 《클래시 로얄》은 완전히 "가위바위보" 게임으로 변질되었습니다! 따라서 모든 경기에서 양측이 승리할 확률은 각각 50%이며, 서로 독립적입니다.

패배한 플레이어들은 당연히 아쉬움이 남습니다. "정신 승리"를 얻기 위해 그들은 "간접 승리"라는 개념을 도입했습니다. $u$가 $v$를 $k$-간접 승리한다는 것은, $k$명의 사람 $a_1, \dots, a_k$가 존재하여 $u$가 $a_1$을 이기고, $a_1$이 $a_2$를 이기고, $a_i$가 $a_{i+1}$을 이기며($\forall i \in [1, k)$), $a_k$가 $v$를 이기는 경우를 의미합니다.

특히, $u$가 $v$를 직접 이겼다면 이를 0-간접 승리라고 합니다.

플레이어들은 새로운 의문을 갖게 되었습니다. 두 플레이어 $u$와 $v$가 주어졌을 때, 최소 몇 단계의 간접 관계를 거쳐야 $u$가 $v$를 이겼다고 할 수 있을까요?

다시 말해, $u$가 $v$를 $k$-간접 승리할 수 있게 하는 최소 정수 $k$를 구해야 합니다. 아쉬움이 남는 플레이어들이 많기 때문에, 당신은 $q$개의 질문에 답해야 합니다.

입력

주의: 본 문제는 입출력 양이 많으므로, C++의 scanf/printf나 cin/cout의 스트림 동기화 해제와 같이 빠른 입출력 방식을 사용하는 것을 권장합니다. 입출력이 느린 언어는 피하는 것이 좋습니다.

첫 번째 줄에 두 정수 $n, q$ ($2 \le n \le 5000, 1 \le q \le 10^5$)가 주어집니다.

다음 $n-1$개의 줄 중 $i$번째 줄은 길이가 $n-i$인 01 문자열입니다. 여기서 $j$번째($1 \le j \le n-i$) 숫자가 1이면 $i$번째 사람이 $i+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$번째 줄에는 $u_i$가 $v_i$를 $k$-간접 승리하게 하는 최소 $k$를 출력합니다. 특히, 어떤 $k$에 대해서도 $u_i$가 $v_i$를 $k$-간접 승리할 수 없다면 -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

예제 출력 1

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

예제 출력 2

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