You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

[丛雨]来到了一个迷宫，这个迷宫是一个 $n × m$ 的网格，第 $i$ 第 $j$ 列的格子会包含一个方向指示 $d(i,j)$ 和一个权值 $v(i,j)$ 。假设起点为格子 $(sx,sy)$（即第 $sx$ 行第 $sy$ 列的格子），一开始丛雨左脚踏入格子 $(sx,sy)$ ，分数加上 $v(sx,sy)$ ，然后该格子的权值变为它的相反数 $−v(sx,sy)$ 。之后有两种选择: (1)结束游戏，当前分数为最终分数。 (2)按照当前格子的方向指示走到下一个格子 $(x,y)$。如果踏入当前格子的是左脚，则右脚踏入 $(x,y)$ ，并且分数减去 $v(x,y)$ ；如果踏入当前格子的是右脚，则左脚踏入 $(x,y)$ ，分数加上 $v(x,y)$ 。之后 $v(x,y)$ 变为它的相反数 $−v(x,y)$ 。然后继续做下一个选择。 注意，必须存在下一个格子才能选择 $(2)$ ，否则只能选择 $(1)$ 。 具体的下一个格子的定义如下： 格子的方向指示由^ v < >四个字符表示，假设当前格子为 $(i,j)$， 如果 $d(i,j)=$^，则表示往上走，即下一个格子为 $(i−1,j)$ ； 如果 $d(i,j)=$v，则表示往下走，即下一个格子为 $(i+1,j)$ ； 如果 $d(i,j)=$<，则表示往左走，即下一个格子为 $(i,j−1)$ ； 如果 $d(i,j)=$>，则表示往右走，即下一个格子为 $(i,j+1)$ ； 如果格子 $(i,j)$ 的下一个格子 $(x,y)$ 不满足 $1 \le x \le n$ 且 $1 \le y \le m$ ，那么认为格子 $(i,j)$ 不存在下一个格子。 丛雨的初始分数为 $0$ ，她想知道，对于每个 $(i,j)$ $(1 \le i \le n, 1 \le j \le m)$ 作为起点，她能得到的最高的最终分数是多少。由于她不想输出文件太大，假设对于每个　$(i,j)$ ，答案为 $ans(i,j)$ ，那么你只需要输出

其中 $B = 10^{15}$ , $C = 2 \times 10^{15} + 21$。如果以某个 $(i, j)$ 为起点，能得到比任意正整数大的最终分数，则令 $ans(i,j) = B$ 。

输入格式（maze.in）

第一行，两个正整数 $n$ , $m$ ，以空格相隔。 接下来 $n$ 行，第 $i$ 行是字符串 $d_i$ ，其第 $j$ 个字符 $d(i,j)$ 表示第 $i$ 行第 $j$ 列格子的方向指示。 接下来 $n$ 行，第 $i$ 行 $m$ 个整数 $v(i,1), v(i,2), ..., v(i,m)$ ，以空格相隔，$v(i,j)$ 表示第 $i$ 行第 $j$ 列格子的初始权值。

输出格式（maze.out）

输出一个整数，表示答案。

输入样例

3 3
><>
>vv
^<<
1 2 3
4 5 6
7 8 9

输出样例

3946712175731523781

样例解释

对应的答案为

1 2 3
7 5 6
8 8 17

数据范围

对于 $10\%$ 的数据，满足 $1 \le n, m \le 10$ 。 对于 $40\%$ 的数据，满足 $1 \le n, m \le 100$ 。 对于 $100\%$ 的数据，满足 $1 \le n, m \le 1000, |v(i,j)| \le 10^9$ 。 注意：由于答案可能较大，对于C/C++语言，你可能需要使用 long long数据类型进行计算。在输出答案时，可能不需要实际的取模，只需要使用unsigned long long数据类型的自然溢出即可。