题目描述

扶苏来到了一个迷宫，这个迷宫是一个 $n$ 行 $m$ 列的数字矩阵，第 $i$ 行第 $j$ 列写有一个数字 $a_{i,j}$。保证 $1 \leq a_{i,j} \leq 4$。

扶苏会在这个迷宫的某一个位置。假设她当前在迷宫的第 $i$ 行第 $j$ 列：

• 如果 $a_{i,j} = 1$，则她会向上移动一行，即 $i$ 减小 $1$。
• 如果 $a_{i,j} = 2$，则她会向下移动一行，即 $i$ 增大 $1$。
• 如果 $a_{i,j} = 3$，则她会向左移动一列，即 $j$ 减小 $1$。
• 如果 $a_{i,j} = 4$，则她会向右移动一列，即 $j$ 增大 $1$。

初始时和每次移动到另一个格子后，她都会按上述的规则继续进行新的移动。

当她移动出迷宫，即到达第 $0$ 行、第 $0$ 列、第 $n+1$ 行、第 $m+1$ 列时，称她离开了迷宫。

现在，你要回答 $q$ 次询问，每次给定一个扶苏的初时位置，你要回答她在多少次移动后会离开迷宫，或报告她永远不会离开迷宫。

输入格式

第一行是三个整数，表示迷宫的行数 $n$、列数 $m$ 和询问数 $q$。
接下来 $n$ 行，每行 $m$ 个整数，表示矩阵 $a$。
接下来 $q$ 行，每行两个整数 $x_i,y_i$，表示一次查询初时在第 $x_i$ 行 $y_i$ 列时她离开迷宫需要的步数。

输出格式

输出 $q$ 行，每行一个整数，表示一次查询的答案。如果本次查询她永远无法离开迷宫，输出 $-1$。

3 4 3
1 2 3 4
4 3 2 1
2 3 4 1
2 3
2 4
1 3

5
2
-1

提示

• 对 $20\%$ 的数据，$n = 1$。
• 另有 $20\%$ 的数据，$m = 1$。
• 另有 $30\%$ 的数据，查询的答案都不是 $-1$。
• 对全部的测试数据，保证 $1 \leq n, m,q \leq 100$，$1 \leq a_i \leq 4$，$1 \leq x_i \leq n$，$1 \leq y_i \leq m$。