题目背景

译自 ICPC 2024 Yokohama Regional Contest。

题目描述

您是否在为您的孩子寻找数学教育工具？然后，不妨试试这款神奇的产品 E-circuit？这是学习二维几何、逻辑和算术的最佳玩具！

E-circuit 由一个带有多个方块的网格空间组成，这些方块称为单元。每个单元都可以完美地契合在网格的一个方格中。它们具有若干输入和/或输出端子，用于传递整数值。当若干单元在网格中被恰当地放置时，它们会构成一棵表示数学公式的树。单元具有不同的功能，每种功能由下列单个字符表示：

• 数字（$\texttt{0}$ 到 $\texttt{9}$）：这些单元有一个输出端子。它们将该数字所表示的整数值发送到它的输出端子。
• 连接器（$\texttt{\#}$）：这些单元有一个输入端子和一个输出端子。它们接收来自输入端子的整数值，并不做任何改动地将该值发送到输出端子。
• 运算符（$\texttt{+}$，$\texttt{-1}$，$\texttt{*}$，$\texttt{/}$）：这些单元有两个输入端子和一个输出端子，对从输入端接收的值进行以下计算，并将结果发送到输出端子。
  • $\texttt{+}$ 运算符计算两个输入值之和。
  • $\texttt{-}$ 运算符计算两个输入值之差，用较大值减去较小值。
  • $\texttt{*}$ 运算符计算两个输入值之积。
  • $\texttt{/}$ 运算符计算两个输入值之商，用较大值除以较小值，若有小数则截断。
• 打印机（$\texttt{P}$）：打印机有一个输入端子，并显示其输入的值。网格中恰好应有一个打印机单元。

如果两个单元所在的格子共用一条边，则称它们相邻。当两个单元放置在相邻的格子中时，它们会通过一个单元的输出端子和另一个单元的输入端子相连。

现在给定一个恰当放置的单元配置，其中所有单元构成一棵表示数学公式的树。此类放置的形式化描述将在「输入」部分给出。

你的任务是计算该配置下打印机所显示的值。

输入格式

仅一组数据，格式如下所示：

$n$ $m$
$x_{1,1}$ $\cdots$ $x_{1,m}$
$\vdots$
$x_{n,1}$ $\cdots$ $x_{n,m}$

第一行的两个整数 $n$ 和 $m$（$1 \le n \le 50$，$1 \le m \le 50$）表示网格为 $n \times m$ 的矩阵。接下来的 $n$ 行描述单元的放置情况。字符 $x_{i,j}$ （$1 \le i \le n$, $1 \le j \le m$）指定位于从上往下第 $i$ 行、从左往右第 $j$ 列的格子中的单元。每个字符要么表示题目中描述的单元功能，要么是字符 $\texttt{.}$（点），表示该格子为空。

保证单元放置恰当，即：

• 每个单元的相邻单元数等于其输入端子和输出端子总数；
• 所有单元的输入端子总数等于输出端子总数；
• 所有单元都属于打印机树：当且仅当一个单元是打印机或与另一个属于打印机树的单元相邻时，该单元才属于打印机树。

还保证 $\texttt{/}$ 运算符的输入值不为零，并且没有单元的输出值超过 $10^{18}$。

输出格式

输出一行，即打印机显示的值。

6 8
3.......
#....P..
#....#.2
#.###*#+
##-....#
..1...4#

12

4 3
.4.
./P
9*.
.#7

15

5 11
8...8.....8
#.###...###
#.#...P.#..
#**##-*+/##
.4...3.0..1

2024