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$）。