在过去的一年里，几乎每个人都玩过 2048 游戏。很快，获胜的秘诀被揭开，人们对这个游戏的兴趣也逐渐消退。然而，开发人员现在正在致力于该游戏的新改版。未来发展的一个重要方向是增加游戏棋盘的尺寸以及提高最终得分。

然而，为了选择最佳的棋盘尺寸，需要在大大小小的棋盘上多次模拟游戏过程，以估算在新的条件下达到目标所需的步数，并估算可能获得的得分。

你需要编写一个程序，根据一次游戏过程的描述，确定最终的得分。输入包括：棋盘尺寸、初始方块的位置和数值、玩家的移动序列以及每次移动后棋盘上出现的新方块的描述。

对于那些不熟悉这款热门游戏的新手，游戏规则如下。2048 在一个 $N \times N$ 的网格棋盘上进行，棋盘上有带数字的方块，当玩家使用四个方向键移动它们时，所有方块都会向对应方向滑动。在每次移动后，一个数值为 2 或 4 的新方块会随机出现在棋盘的空位上。方块会沿选择的方向尽可能滑动，直到被另一个方块或棋盘边缘阻挡。如果两个数值相同的方块在移动过程中相撞，它们将合并为一个数值为两者之和的新方块。在同一次移动中，合并后产生的新方块不能再次与其他方块合并。方块的移动和合并是按照移动方向上从最前到最后（即最靠近移动方向终点到最远离终点）的顺序依次处理的。例如，向右移动后，行 2 2 _ 2 _ 会变成 _ _ _ 2 4，行 2 2 2 2 2 2 会变成 _ _ _ 4 4 4。

玩家的得分从零开始，每当两个方块合并时，得分就会增加新合并方块的数值。

输入格式

输入的第一行包含一个整数 $N$，表示棋盘的尺寸（$4 \le N \le 100$）。

第二行包含一个整数 $K$，表示棋盘上已有的初始方块数量（$0 \le K \le N^2$）。

接下来的 $K$ 行中，每行包含三个整数，用于描述棋盘上的方块：方块上的数字（2 的 1 次方到 10 次方之一，即 2 到 1024）以及该方块在棋盘上的坐标：行和列。行号从上到下从 1 开始编号，列号从左到右从 1 开始编号。保证给定的方块占用了棋盘上 $K$ 个不同的格子。

之后，单独的一行给出一个整数 $L$，表示游戏过程中玩家的移动次数（$0 \le L \le 10\,000$）。

接下来的 $L$ 行按顺序包含玩家移动的描述，每行一个描述。一次移动的描述以字符 L（左）、R（右）、U（上）或 D（下）之一开始。接着是三个由单个空格分隔的整数，它们定义了玩家移动后在棋盘上出现的新方块：数值（2 或 4）以及该方块的坐标：行和列。保证在每次玩家移动后，新方块都会放置在棋盘的空位上。

输出格式

输出一个整数：输入所描述的游戏结束时的最终得分。

样例

输入样例 1

6
5
2 1 2
2 1 3
4 1 5
4 1 6
2 3 1
2
L 4 2 1
U 2 6 2

输出样例 1

20

输入样例 2

4
4
1024 1 1
1024 1 2
1024 2 1
1024 2 2
2
D 4 1 1
R 4 1 1

输出样例 2

8192