题目描述

小航被困在一个 $n$ 行 $m$ 列的数字网格中，第 $i$ 行第 $j$ 列写着一个数字 $a_{i,j}$，保证 $1 \leq a_{i,j} \leq 4$。

小航的移动规则取决于当前格子的数字：

• 若 $a_{i,j} = 1$，向上走一格，即行号减 $1$。
• 若 $a_{i,j} = 2$，向下走一格，即行号加 $1$。
• 若 $a_{i,j} = 3$，向左走一格，即列号减 $1$。
• 若 $a_{i,j} = 4$，向右走一格，即列号加 $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$。