Intersections [B] - Problème

The largest city in Bytotia, Bytopolis, is famous for its rich network of streets. Consequently, the life of pedestrians can be quite difficult.

Bytopolis has $n + m$ streets; $n$ of them (called horizontal) run from west to east, and the remaining $m$ (called vertical) run from north to south. Each horizontal street intersects every vertical street, creating a total of $n \cdot m$ intersections, arranged in an $n \times m$ rectangle. We will denote the intersection of the $i$-th horizontal street from the north and the $j$-th vertical street from the west as $(i, j)$.

Bytopolis also contains $(n + 1) \cdot (m + 1)$ squares, arranged in an $(n + 1) \times (m + 1)$ rectangle, through which pedestrians can move. These squares are also denoted by pairs of numbers $(a, b)$, where $0 \le a \le n$ and $0 \le b \le m$. The intersection $(i, j)$ is adjacent to the square $(i - 1, j - 1)$ to the northwest, $(i - 1, j)$ to the northeast, $(i, j - 1)$ to the southwest, and $(i, j)$ to the southeast. Each square is therefore adjacent to a certain number of streets, between two and four.

At each intersection, a traffic light system is installed, connected to the four pedestrian crossings located at that intersection. Thus, in Bytopolis, there are $4 \cdot n \cdot m$ pedestrian crossings. Thanks to the traffic light system installed at intersection $(i, j)$, in each minute: Either green lights are on at the two crossings across the horizontal street, i.e., at the crossings connecting squares $(i - 1, j - 1)$ with $(i, j - 1)$ and $(i - 1, j)$ with $(i, j)$, Or green lights are on at the two crossings across the vertical street, i.e., at the crossings connecting squares $(i - 1, j - 1)$ with $(i - 1, j)$ and $(i, j - 1)$ with $(i, j)$.

The traffic light system was activated simultaneously at all intersections in Bytopolis. In honor of this event, the residents of Bytopolis measure time in minutes from the system's activation.

The traffic light at each intersection operates on a cycle basis. Intersection $(i, j)$ is configured with a binary word $s_{i,j}$ determining which crossings at this intersection have a green light. The characters of this word are indexed from $0$ to $|s_{i,j}| - 1$, where $|s_{i,j}|$ is its length. To determine which crossings at intersection $(i, j)$ have a green light in the $t$-th minute from the system's activation ($t \ge 0$), the system calculates $r := t \pmod{|s_{i,j}|}$ – the remainder of dividing $t$ by the length of the word $s_{i,j}$. Then: If the $r$-th character of the word $s_{i,j}$ is $0$, then throughout the $t$-th minute, the green lights are on at the two crossings at intersection $(i, j)$ that lead across the horizontal street; Otherwise, throughout the $t$-th minute, the green lights are on at the two crossings at intersection $(i, j)$ that cross the vertical street.

Pedestrians in Bytopolis are so tormented by the complicated system of crossings and lights that they have developed the ability to move extremely quickly. In any given minute, they can traverse any number of pedestrian crossings – provided, of course, that the green light is on for them. If a pedestrian wants to cross a passage without a green light, they must wait until the green light turns on. Pedestrians can only wait on the squares.

Your task is to help fully computerize Bytopolis. Your first task is to create a system that will answer queries of the form "if in the $t$-th minute a pedestrian starts from square $(a_i, b_i)$, what is the earliest time they can reach square $(c_i, d_i)$?". Time is money, and pedestrians in Bytopolis are running out of patience. Write a program that, given the information about Bytopolis, will answer the queries!

Input

The first line of the input contains three integers $n, m$ and $q$ ($1 \le n, m \le 15\,000$; $n \cdot m \le 10^6$; $1 \le q \le 10^6$), representing the number of horizontal and vertical streets in Bytopolis, and the number of queries you must answer, respectively.

The next $n$ lines contain the description of the traffic light configuration. The $i$-th of these lines contains $m$ words $s_{i,1}, \dots, s_{i,m}$ ($2 \le |s_{i,j}| \le 8$), consisting only of the characters $0$ and $1$. Each $s_{i,j}$ contains at least one $0$ and at least one $1$.

The next $q$ lines contain the descriptions of the queries; the $i$-th of these lines contains five integers $t_i, a_i, b_i, c_i$ and $d_i$ ($0 \le t \le 10^9$; $0 \le a_i, c_i \le n$; $0 \le b_i, d_i \le m$). These represent a query about a pedestrian starting in the $t_i$-th minute from the system's activation from square $(a_i, b_i)$ and wanting to reach square $(c_i, d_i)$.

Output

The output should contain $q$ lines. The $i$-th line should contain a single integer – the minimum possible minute number in which the pedestrian can reach their destination square in the $i$-th query.

It can be proven that for tests conforming to the input format, an answer always exists for any query.

Examples

Input 1

Output 1

Note

In the first query, the pedestrian can move to square $(1, 0)$ in the zeroth minute, wait there until the first minute, and only then reach the destination through squares $(1, 1)$ and $(1, 2)$.

Below is an illustration of Bytopolis with green lights marked in green, in the zeroth, first, second, and third minutes from the activation of the traffic light system.