该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

伞伞的魔法棋盘上，住着一群活泼的小马。棋盘是 $n×n$ 的方格，每个格子里要么有一匹马（标着数字 1~9），要么是空的（.）。

每匹马都有 跳跃等级：数字越大，跳得越远！

• 等级为 $L$ 的小马，在 一轮行动 中 至少跳 $1$ 次，最多跳 $L$ 次（一次就是走一个“日”字步）。
• 马的走法和国际象棋里的马一样，走“日”字：从 $(i,j)$ 可以跳到 $(i±1,j±2)$ 或 $(i±2,j±1)$，但不能跳出棋盘。

多个马可以同时站在同一个格子上，互不干扰。

现在伞伞有 $q$ 个问题：他想知道，如果让所有小马同时开始跳，最少需要多少轮行动，才能让所有马都聚到指定的格子 $(x_i,y_i)$ 上？小马在到达目标格后仍可在后续轮次继续跳跃，只要最后一轮结束时在目标格即可。

如果无论如何都无法聚到一起（比如某匹马永远跳不到那里），就输出 -1。

注意：每轮中，每匹马都必须跳至少一次，不能偷懒不动哦！

输入格式

从文件 magic.in 读入数据。 第一行两个整数 $n,q$。

接下来 $n$ 行，每行一个长度为 $n$ 的字符串，只包含数字 1~9 或 .。数字表示该格有一匹对应等级的马，. 表示空格。

接下来 $q$ 行，每行两个整数 $x_i,y_i$​，表示询问的目标格子。

输出格式

输出到文件 magic.out。 对于每个询问，输出一个整数表示最少轮数；如果无法达成，输出 -1。

5 10
21.43
2214.
.1...
.....
.....
1 1
2 1
3 1
4 1
5 1
1 5
2 5
3 5
4 5
5 5

3
2
3
4
3
3
2
3
4
3

数据规模与约定

下发文件

下发文件分别对应子任务 $1,2,3$。

对于 $100\%$ 的数据：保证 $1 \leq n,q \leq 300,1 \leq x_i,y_i \leq n$，保证至少有一匹马。

时空限制：$2$ 秒 / $256\,\mathrm{MiB}$。