AT_abc440_g [ABC440G] Haunted House

ハロウィンの季節がやってきました。あなたは肝試しとして、お化け屋敷に挑戦しようとしています。 $ F $ 階だてのお化け屋敷があり、各階は $ H $ 行 $ W $ 列のグリッドで表されます。 $ k $ 階を表すグリッドの上から $ i $ 行目・左から $ j $ 列目のマスをマス $ (k,i,j) $ とします。 マス $ (k,i,j) $ の内容は文字 $ S_{k,i,j} $ によって、以下のように表されます。 - $ S_{k,i,j} $ が数字 (`0` - `9`) の場合、マス $ (k,i,j) $ は空きマスであり、数字が表す $ 1 $ 桁の整数と同じ枚数のコインがある。 - $ S_{k,i,j} $ が `#` の場合、マス $ (k,i,j) $ は壁マスである。 空きマス $ (k,i,j) $ からほかのマス $ (k', i', j') $ に直接移動できる条件は、マス $ (k', i', j') $ が空きマスであり、かつ以下のいずれかを満たすことです。 - $ k' = k $ および $ |i' - i| + |j' - j| = 1 $ を満たす。 - $ (k', i', j') = (k+1, i, j) $ を満たす。 - $ (k', i', j') = (k-1, i, j) $ を満たし、かつマス $ (k,i,j) $ に**ハシゴ**が置かれている。 グリッドの外部に移動することはできません。 $ Q $ 個の質問が与えられるので、それぞれの答えを求めてください。 $ i $ 個目の質問 ( $ 1 \leq i \leq Q $ ) は以下の通りです。 - 好きな空きマスを $ 1 $ つだけ選んでハシゴを置いてから、マス $ (G_i, A_i, B_i) $ を開始地点として移動を繰り返したとき、訪れたマスにあるコインの合計枚数の最大値を求めよ。 なお、各質問は独立です。つまり、ある質問で置いたハシゴは、ほかの質問に影響を与えません。

入力は以下の形式で標準入力から与えられる。 > $ 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 $

$ Q $ 行出力せよ。 $ i $ 行目 ( $ 1 \leq i \leq Q $ ) には $ i $ 個目の質問の答えを出力せよ。

### Sample Explanation 1 $ 1 $ 番目の質問において、マス $ (2,3,5) $ にハシゴを置いた状態で以下のように移動することで、訪れたマスにあるコインの合計枚数を $ 47 $ にすることができます。 1. お化け屋敷の $ 1 $ 階において、マス $ (1,2,3) $ から開始する。 2. お化け屋敷の $ 2 $ 階に上がり、マス $ (2,2,3) \to (2,2,4) \to (2,2,5) \to (2,3,5) $ の順に移動する。 3. お化け屋敷の $ 1 $ 階に降りて、マス $ (1,3,5) \to (1,4,5) \to (1,4,4) \to (1,3,4) \to (1,4,4) $ の順に移動する。 4. お化け屋敷の $ 2 $ 階に上がり、マス $ (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. お化け屋敷の $ 3 $ 階に上がり、マス $ (3,4,4) \to (3,4,5) $ の順に移動する。 $ 2 $ 番目の質問において、マス $ (2,4,4) $ にハシゴを置いた状態で以下のように移動することで、訪れたマスにあるコインの合計枚数を $ 34 $ にすることができます。 1. お化け屋敷の $ 2 $ 階において、マス $ (2,3,2) \to (2,4,2) \to (2,4,3) \to (2,4,4) $ の順に移動する。 2. お化け屋敷の $ 1 $ 階に降りて、マス $ (1,4,4) \to (1,4,5) \to (1,3,5) \to (1,3,4) \to (1,4,4) $ の順に移動する。 3. お化け屋敷の $ 2 $ 階に上がり、マス $ (2,4,4) $ にいる。 4. お化け屋敷の $ 3 $ 階に上がり、マス $ (3,4,4) \to (3,4,5) $ の順に移動する。 $ 3 $ 番目の質問において、どのようにハシゴを置いても開始地点のマス $ (3,2,2) $ から移動することはできません。 ### Constraints - $ F,H,W $ は整数 - $ 1 \leq F \leq 10 $ - $ 1 \leq H,W \leq 500 $ - $ S_{k,i,j} $ は数字 (`0`, `1`, `2`, `3`, `4`, `5`, `6`, `7`, `8`, `9`) または `#` のいずれか ( $ 1 \leq k \leq F, 1 \leq i \leq H, 1 \leq j \leq W $ ) - $ Q $ は整数 - $ 1 \leq Q \leq 10^5 $ - $ G_i, A_i, B_i $ は整数 ( $ 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} $ は `#` でない ( $ 1 \leq i \leq Q $ )