Huarongdao

Little B has recently become obsessed with Huarongdao, but he always spends a long time completing it. Therefore, he wants to use programming to complete Huarongdao: given a configuration, determine if the Huarongdao puzzle can be completed, and if so, what is the minimum time required.

The Huarongdao game played by Little B is different from the classic version. The rules are as follows:

1. On an $n \times m$ board, there are $n \times m$ cells, among which exactly one cell is empty, and the remaining $n \times m - 1$ cells each contain a piece. Each piece has a size of $1 \times 1$.
2. Some pieces are fixed, while others can be moved.
3. Any piece adjacent to the empty cell (sharing a common edge) can be moved into the empty cell.

The goal of the game is to move a specific piece to a target position.

Given a board, you can play $q$ games. In each game, the fixed pieces on the board do not change, but the initial position of the empty cell, the initial position of the designated movable piece, and the target position may differ. In the $i$-th game, the empty cell is at row $EX_i$, column $EY_i$, the initial position of the designated movable piece is at row $SX_i$, column $SY_i$, and the target position is at row $TX_i$, column $TY_i$.

Assume that Little B can perform one piece movement per second, and the time for other operations is negligible. Please tell Little B the minimum time required for each game, or tell him that it is impossible to complete the game.

Input

The first line contains three integers separated by spaces, representing $n$, $m$, and $q$.

The next $n$ lines describe the $n \times m$ board. Each line contains $m$ integers separated by spaces. Each integer describes the state of the piece on that cell: $0$ indicates that the piece on this cell is fixed, and $1$ indicates that the piece on this cell can be moved or the cell is empty.

The next $q$ lines each contain 6 integers: $EX_i$, $EY_i$, $SX_i$, $SY_i$, $TX_i$, and $TY_i$, separated by spaces, representing the position of the empty cell, the initial position of the designated piece, and the target position, respectively.

Output

Output $q$ lines, each containing one integer representing the minimum time required for each game. If a game cannot be completed, output $-1$.

Examples

Input 1

3 4 2
0 1 1 1
0 1 1 0
0 1 0 0
3 2 1 2 2 2
1 2 2 2 3 2

Output 1

2
-1

Note

The cells marked with an 'X' are fixed, the red cells are the target positions, and the circles represent pieces, where the green circle represents the target piece.

1. In the first game, the initial position of the empty cell is $(3, 2)$. The goal is to move the piece initially at $(1, 2)$ (the piece represented by the green circle) to the position $(2, 2)$ (the red cell).

2. In the second game, the initial position of the empty cell is $(1, 2)$. The goal is to move the piece initially at $(2, 2)$ (the piece represented by the green circle) to the position $(3, 2)$.

To move a designated piece to the target position, one must first move the empty cell to the target position. The empty cell must move to the target position, which necessarily involves swapping with the piece currently at the target position in the diagram. After that, it can only swap with the piece that was originally at the target position. Therefore, the target piece can never reach its target position, and the game cannot be completed.

Constraints

• For 30% of the data, $1 \le n, m \le 10$, $q = 1$.
• For 60% of the data, $1 \le n, m \le 30$, $q \le 10$.
• For 100% of the data, $1 \le n, m \le 30$, $q \le 500$.

Figure 1. The Huarongdao board configuration for the first game.