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`），则该单元格为空白单元格，内含的硬币数量等于该数字对应的一位整数。 - 若 $S_{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$）要求如下： - 选择恰好一个空白单元格放置梯子，从单元格 $(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$ 行输出第 $i$ 次询问的答案。

### 样例解释 1 对于第一次询问，在单元格 $(2,3,5)$ 放置梯子并按以下方式移动，可收集到的硬币总数为 $47$： 1. 从第一层的单元格 $(1,2,3)$ 出发； 2. 向上移动到第二层，按顺序移动：$(2,2,3) \to (2,2,4) \to (2,2,5) \to (2,3,5)$； 3. 向下移动到第一层，按顺序移动：$(1,3,5) \to (1,4,5) \to (1,4,4) \to (1,3,4) \to (1,4,4)$； 4. 向上移动到第二层，按顺序移动：$(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,4,4) \to (3,4,5)$。 对于第二次询问，在单元格 $(2,4,4)$ 放置梯子，按照以下步骤移动，你收集到的经过单元格的硬币总数可以达到 $34$： 1. 在第二层按顺序移动：$(2,3,2) \to (2,4,2) \to (2,4,3) \to (2,4,4)$； 2. 向下移动到第一层，再按顺序移动：$(1,4,4) \to (1,4,5) \to (1,3,5) \to (1,3,4) \to (1,4,4)$； 3. 向上移动回到第二层，到达单元格 $(2,4,4)$； 4. 向上移动到第三层，再按顺序移动：$(3,4,4) \to (3,4,5)$。 对于第三次询问，无论你将梯子放置在哪个单元格，都无法从起点单元格 $(3,2,2)$ 移动到其他位置。 ### 数据范围 - $F,H,W$ 为整数； - $1 \leq F \leq 10$； - $1 \leq H,W \leq 500$； - $S_{k,i,j}$ 为数字（`0`-`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$）。