题目描述

题目译自 PA 2021 Runda 4 Skrzyżowania

Byteotia 的最大城市 Bytopolis 以其丰富的街道网络而闻名。因此，行人的生活可能非常困难。

Bytopolis 共有 $n+m$ 条街道，其中 $n$ 条从西到东，称为横向街道，其余 $m$ 条从南到北，称为纵向街道。每条横向街道与每条纵向街道都相交，形成了总共 $n\cdot m$ 个路口，这些路口按 $n\times m$ 的矩形网格排布。我们将从北数第 $i$ 条横向道路和从西数第 $j$ 条纵向道路形成的路口称为 $(i,j)$。

Bytopolis 还有 $(n+1)\cdot(m+1)$ 个广场，按 $(n+1)\times (m+1)$ 的矩形网格排布，行人可以在广场上行走。我们同样用一个数对 $(a,b)$ 表示每一个广场，其中 $0\le a\le n,0\le b\le m$。路口 $(i,j)$ 与广场 $(i-1,j-1)$ 的西北角，广场 $(i-1,j)$ 的东北角，广场 $(i,j-1)$ 的西南角，广场 $(i,j)$ 的东南角相邻。每个广场与两条或四条街道相邻。

每个路口都有四个人行横道，每个人行横道都配有一套红绿灯系统。因此，在 Bytopolis 有 $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)$ 的路口。

Bytopolis 的所有路口同时启动了红绿灯系统。为了纪念这一事件，从这个红绿灯系统启动开始，Bytopolis 居民开始按分钟测量时间。

每个路口的红绿灯都是按周期工作的。路口 $(i,j)$ 配置了一个二进制串 $s_{i,j}$。我们用从 $0$ 到 $|s_{i,j}|-1$ 的整数给二进制串中的每个位从左到右标号，其中 $|s_{i,j}|$ 是这个二进制串的长度。为了确定在系统启动后的第 $t$ 分钟（$t\ge 0$）哪些路口 $(i,j)$ 哪里亮绿灯，这个系统会计算 $r:=t\bmod |s_{i,j}|$——二进制串 $s_{i,j}$ 的长度除以 $t$ 的余数。然后：

• 如果二进制串 $s_{i,j}$ 的第 $r$ 位是 $\texttt 0$，对于路口 $(i,j)$，在第 $t$ 分钟内横向街道的两个路口亮绿灯；
• 否则，在第 $t$ 分钟内纵向街道的两个路口亮绿灯。

Bytopolis 的居民困惑于这种复杂的路口和红绿灯系统，以至于他们变得可以迅速移动。他们每分钟可以穿过任何数量的人行道——当然，只要路口亮绿灯。如果一个居民想要在路口不是绿灯的情况下穿过人行道，他必须等到绿灯亮的时候才能通过。居民们只能在广场上等待。

你的任务是让 Bytopolis 计算化。你的第一个任务是编写一个系统，回答「如果一个行人在第 $t$ 分钟从广场 $(a_i,b_i)$ 出发，他最早什么时候可以到达广场 $(c_i,d_i)$？」时间就是金钱，Bytopolis 的居民已经没有耐心了。所以给定 Bytopolis 的信息，请编写程序回答这些询问。

输入格式

输入的第一行包含三个正整数 $n,m,q\ (1\le n,m\le 15\ 000,n\cdot m\le 10^6,1\le q\le 10^6)$，表示 Bytopolis 的横向和纵向街道条数和要回答的询问个数。

接下来 $n$ 行描述红绿灯信息。第 $i$ 行有 $m$ 个二进制串 $s_{i,1},\ldots,s_{i,m}\ (2\le |s_{i,j}|\le 8)$，二进制串中只包含 $\texttt 0$ 和 $\texttt 1$。保证每个 $s_{i,j}$ 中都至少出现一个 $\texttt 0$ 和一个 $\texttt 1$。

接下来 $q$ 行每行描述一个询问。第 $i$ 行包含五个整数 $t_i,a_i,b_i,c_i,d_i\ (0\le t_i\le 10^9,0\le a_i,c_i\le n,0\le b_i,d_i\le m)$。表示一个行人在第 $t$ 分钟从广场 $(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