有一台奇特的计算机，它只能存储一个变量 $n$ 和执行三种操作。

操作 $U$：如果 $n = 1$，则无视该操作。否则执行 $n = n / 2$（即将 $n$ 赋值为 $n / 2$ 向下取整）。

操作 $L$：执行 $n = n * 2$（即将 $n$ 赋值为 $n * 2$）。

操作 $R$：执行 $n = n * 2 + 1$（即将 $n$ 赋值为 $n * 2 + 1$）。

变量 $n$ 初始值为 $1$。

现在给你 $N + M$ 个程序。每个程序由一个二元组 $(x,c)$ 组成，其中 $x$ 是整数，$c$ 是字符 $U$、$L$、$R$ 三种中的一种，表示在计算机上连续执行 $x$ 次操作 $c$（若 $x$ 为 $0$ 表示不执行任何操作）。

你需要按编号从小到大依次执行这 $N + M$ 个程序，其中前 $N$ 个程序的 $x$ 是已知的，而后 $M$ 个程序的 $x$ 已经丢失了，你只知道 $x$ 在范围 $[0,t]$ 之间（即 $x$ 可能为大于等于 $0$ 小于等于 $t$ 的所有整数）。

请问将这 $N + M$ 个程序执行完毕后，变量 $n$ 有多少种可能的不同取值？

输入格式

第一行为 $2$ 个整数 $N、M$ 。

接下来 $N$ 行每行为一个整数 $x$ 和一个字符 $c$。

接下来 $M$ 行每行为一个整数 $t$ 和一个字符 $c$。

输出格式

输出将这 $N + M$ 个程序执行完毕后，变量 $n$ 有多少种可能的不同取值。

样例

input

2 2
1 L
1 L
1 R
3 U

output

4

hint

初始 $n = 1$。

执行第一个程序后 $n = 2$。

执行第二个程序后 $n = 4$。

执行第三个程序后 $n = 4 或 9$。

执行第四个程序后 $n = 1 或 2 或 4 或 9$。

程序全部执行完毕后变量 $n$ 有 $4$ 种可能的取值。

限制与约定

设 $S = \max(\sum x,\sum t)$，即前 $N$ 种程序的 $x$ 之和与后 $M$ 种程序的 $t$ 之和的较大值。

对于 $30\texttt{%}$ 的数据：$1 \leq S \leq 20$。

对于 $50\texttt{%}$ 的数据：$1 \leq S \leq 60$。

另有 $30\texttt{%}$ 的数据：所有程序仅包含操作 $L$ 和操作 $R$。

对于 $100\texttt{%}$ 的数据：$1 \leq N、M \leq 2501$，$0 \leq x、t \leq 10^8$，$c$ 是字符 $U$、$L$、$R$ 三种中的一种。

时间限制：$1\texttt{s}$

空间限制：$128\texttt{MB}$