AT_abc440_g [ABC440G] Haunted House

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.

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 $ Q $ lines. The $ i $ -th line ( $ 1 \leq i \leq Q $ ) should contain the answer to the $ i $ -th question.

### Sample Explanation 1 For the first question, by placing a ladder at cell $ (2,3,5) $ and moving as follows, you can make the total number of coins in the visited cells $ 47 $ : 1. Start at cell $ (1,2,3) $ on the first floor. 2. Go up to the second floor and move in the order $ (2,2,3) \to (2,2,4) \to (2,2,5) \to (2,3,5) $ . 3. Go down to the first floor and move in the order $ (1,3,5) \to (1,4,5) \to (1,4,4) \to (1,3,4) \to (1,4,4) $ . 4. Go up to the second floor and move in the order $ (2,4,4) \to (2,4,3) \to (2,4,2) \to (2,3,2) \to (2,4,2) \to (2,4,3) \to (2,4,4) $ . 5. Go up to the third floor and move in the order $ (3,4,4) \to (3,4,5) $ . For the second question, by placing a ladder at cell $ (2,4,4) $ and moving as follows, you can make the total number of coins in the visited cells $ 34 $ : 1. Move in the order $ (2,3,2) \to (2,4,2) \to (2,4,3) \to (2,4,4) $ on the second floor. 2. Go down to the first floor and move in the order $ (1,4,4) \to (1,4,5) \to (1,3,5) \to (1,3,4) \to (1,4,4) $ . 3. Go up to the second floor and be at cell $ (2,4,4) $ . 4. Go up to the third floor and move in the order $ (3,4,4) \to (3,4,5) $ . For the third question, no matter how you place the ladder, you cannot move from the starting cell $ (3,2,2) $ . ### 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 $ )