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

题目描述

某自动导航系统由一个 $n$ 行 $m$ 列的网格组成。第 $i$ 行第 $j$ 列的格子中记录了一个整数 $a_{i,j}$，并且保证 $1\leq a_{i,j}\leq 4$。

每个数字代表一个固定的移动方向。假设导航装置当前位于第 $i$ 行第 $j$ 列，则它会按照当前格子中的数字移动一步：

• 如果 $a_{i,j}=1$，向上移动一行，即移动到 $(i-1,j)$；
• 如果 $a_{i,j}=2$，向下移动一行，即移动到 $(i+1,j)$；
• 如果 $a_{i,j}=3$，向左移动一列，即移动到 $(i,j-1)$；
• 如果 $a_{i,j}=4$，向右移动一列，即移动到 $(i,j+1)$。

每次进入一个新的格子后，导航装置都会继续按照新格子中记录的方向移动。

当导航装置移动到网格范围之外时，称它成功离开网格。也就是说，当它到达第 $0$ 行、第 $n+1$ 行、第 $0$ 列或第 $m+1$ 列时，移动过程结束。

现在共有 $q$ 次询问。每次询问给出一个起始格子，请你判断：

• 导航装置经过多少次移动后会离开网格；
• 如果它会一直在网格内部循环移动，永远无法离开，则输出 $-1$。

每次询问相互独立，均从给定的起始位置重新开始移动。

输入格式

第一行输入三个整数 $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,j}\leq 4$，$1\leq x_i\leq n$，$1\leq y_i\leq m$。