城市里有 $n+m$ 条道路, 其中 $n$ 条水平的道路连接东西两个方向, $m$ 条竖直的道路连接南北两个方向. 每条水平的道路和每条竖直的道路之间有一个交点, 使得总共有 $n \cdot m$ 个交点, 构成了一个 $n \times m$ 的矩形. 我们记第 $i$ 条水平道路和第 $j$ 条数值道路之间的交点为 $(i,j)$.
城市里就这样被划分成了 $(n+1) \times (m+1)$ 个广场, 每个广场可以用 $(a, b)$ 来表示 $(0 \leq a \leq n, 0 \leq b \leq m)$. 其中交点 $(i,j)$ 与广场 $(i-1,j), (i,j-1), (i,j),(i-1,j-1)$ 相邻. 因此, 每个广场都被一些道路包围, 且道路的数量为 $2 \sim 4$ 条.
每个交叉路口都有一个红绿灯系统, 与位于改交叉路口的四个人行道相连. 即在城市中, 我们有 $4 \cdot n \cdot m$ 条人行道. 对于安装在 $(i,j)$ 的红绿灯系统, 每分钟:
- 要么在水平方向的街道上亮起绿灯, 即连接 $(i-1,j-1)$ 与 $(i,j-1)$ 的道路和连接 $(i-1,j)$ 与 $(i,j)$ 的道路上亮起绿灯.
- 要么在竖直方向上的街道亮起绿灯, 即连接 $(i-1,j-1)$ 与 $(i-1,j)$ 的道路和连接 $(i,j-1)$ 与 $(i,j)$ 的道路上亮起绿灯.
在时刻 $0$ 的时候, 所有的红绿灯同时启动. 每个十字路口的红绿灯系统都是按周期运行的. 十字路口 $(i,j)$ 有一个对应的二进制字符串 $s_{i,j}$, 指定这个十字路口中哪个方向是绿灯. 具体地, 对 $0$ 到 $|s_{i,j}|-1$ ($|s_{i,j}|$ 表示该串的长度), 为了确定在第 $t$ 分钟 ($t \geq 0$) 时哪个方向亮了绿灯, 红绿灯系统会计算 $r = t \bmod |s_{i,j}|$ - 即 $t$ 除以 $|s_{i,j}|$ 的余数, 然后:
- 如果 $s_{i,j}$ 的第 $r$ 个字符为
0, 那么在第 $t$ 分钟内, 路口 $(i,j)$ 两条水平方向的街道是绿灯. - 否则, 在第 $t$ 分钟内, 路口 $(i,j)$ 的两条竖直方向的街道是绿灯.
由于你被复杂的十字路口和红绿灯系统所困扰, 你已经发展出了非常强大的移动能力. 你每分钟可以穿过任意数量的人行道 - 只要它们是绿灯亮起的状态. 如果你想要穿过一条当前不是绿灯的街道, 那么你只能在广场中等待, 直到这条街道亮起绿灯.
你的任务是回答若干个问题, 每个问题形如 "如果在第 $t$ 分钟时, 一个行人从广场 $(a_i,b_i)$ 出发, 那么他最早在什么时刻才能达到广场 $(c_i,d_i)$"?
输入格式
输入的第一行包含三个整数 $n,m$ 和 $q$ ($1 \leq n,m \leq 15~ 000, n \cdot m \leq 10^6, 1 \leq q \leq 10^6$), 分别表示水平街道的数量, 竖直街道的数量, 以及询问的数量.
接下来的 $n$ 行, 描述所有红绿灯的状态. 在这些行中的第 $i$ 行中, 包含 $m$ 个只包含 0 和 1 的字符串 $s_{i,1},\cdots, s_{i,m} (2 \leq |s_{i,j}| \leq 8)$. 保证每个 $s_{i,j}$ 至少包含一个 0 和一个 1.
接下来的 $q$ 行, 每行描述一个询问. 在这些行中的第 $i$ 行中, 包含五个整数 $t_i,a_i,b_i,c_i$ 和 $d_i$ ($0 \leq t \leq 10^9, 0\leq a_i,c_i \leq n, 0 \leq b_i,d_i \leq m$). 它们表示一组询问, 其中你在第 $t_i$ 时刻从广场 $(a_i,b_i)$ 出发, 想要抵达广场 $(c_i,d_i)$.
输出格式
输出包含恰好 $q$ 行, 其中的第 $i$ 行包含一个整数 - 第 $i$ 组询问的答案. 可以证明如果测试数据符合输入格式, 那么任意询问的答案都是存在的.
样例数据
样例输入
2 2 7
01 1100
001 10
0 0 0 2 2
1 0 1 2 1
5 2 1 0 0
0 0 2 2 2
15 1 1 0 0
16 1 1 0 0
7 2 2 2 2样例输出
1
3
6
0
15
17
7