Problem Statement

Halloween season has arrived. As a test of courage, you are about to challenge a haunted house.

There is a haunted house with $F$ floors, and each floor is represented by an $H$-row by $W$-column grid. Let cell $(k,i,j)$ be the cell at the $i$-th row from the top and $j$-th column from the left of the grid representing floor $k$.

The content of cell $(k,i,j)$ is represented by the character $S_{k,i,j}$ as follows:

• If $S_{k,i,j}$ is a digit (0 - 9), cell $(k,i,j)$ is an empty cell with a number of coins equal to the single-digit integer represented by the digit.
• If $S_{k,i,j}$ is #, cell $(k,i,j)$ is a wall cell.

You can move directly from an empty cell $(k,i,j)$ to another cell $(k', i', j')$ if cell $(k', i', j')$ is an empty cell and one of the following is satisfied:

• $k' = k$ and $|i' - i| + |j' - j| = 1$ are satisfied.
• $(k', i', j') = (k+1, i, j)$ is satisfied.
• $(k', i', j') = (k-1, i, j)$ is satisfied, and a ladder is placed at cell $(k,i,j)$.

You cannot move outside the grid.

You are given $Q$ questions; answer each of them. The $i$-th question ($1 \leq i \leq Q$) is as follows:

• Find the maximum total number of coins in the cells you visit if you choose exactly one empty cell and place a ladder there, start at cell $(G_i, A_i, B_i)$, and repeatedly move.

Each question is independent. That is, a ladder placed for one question does not affect other questions.

Constraints

• $F,H,W$ are integers.
• $1 \leq F \leq 10$
• $1 \leq H,W \leq 500$
• $S_{k,i,j}$ is either a digit (0, 1, 2, 3, 4, 5, 6, 7, 8, 9) or #. ($1 \leq k \leq F, 1 \leq i \leq H, 1 \leq j \leq W$)
• $Q$ is an integer.
• $1 \leq Q \leq 10^5$
• $G_i, A_i, B_i$ are integers. ($1 \leq i \leq Q$)
• $1 \leq G_i \leq F$ ($1 \leq i \leq Q$)
• $1 \leq A_i \leq H$ ($1 \leq i \leq Q$)
• $1 \leq B_i \leq W$ ($1 \leq i \leq Q$)
• $S_{G_i, A_i, B_i}$ is not #. ($1 \leq i \leq Q$)

Input

The input is given from Standard Input in the following format:

F H W
S_{1,1,1} S_{1,1,2} \cdots S_{1,1,W}
S_{1,2,1} S_{1,2,2} \cdots S_{1,2,W}
\vdots
S_{1,H,1} S_{1,H,2} \cdots S_{1,H,W}
S_{2,1,1} S_{2,1,2} \cdots S_{2,1,W}
S_{2,2,1} S_{2,2,2} \cdots S_{2,2,W}
\vdots
S_{2,H,1} S_{2,H,2} \cdots S_{2,H,W}
\vdots
S_{F,1,1} S_{F,1,2} \cdots S_{F,1,W}
S_{F,2,1} S_{F,2,2} \cdots S_{F,2,W}
\vdots
S_{F,H,1} S_{F,H,2} \cdots S_{F,H,W}
Q
G_1 A_1 B_1
G_2 A_2 B_2
\vdots
G_Q A_Q B_Q

Output

Output $Q$ lines. The $i$-th line ($1 \leq i \leq Q$) should contain the answer to the $i$-th question.