阿拉丁对皇宫里的生活感到厌倦了。他有一份稳定的工作，妻子茉莉（Jasmine），孩子们也即将出生，生活正变得单调乏味。在这一切的驱使下，他决定在安顿下来之前再进行一次冒险。

他决定去寻找黄金梨（Golden Pear），这是一种极其珍贵的传说中的神器，至今无人能够找到。

阿拉丁搜寻的沙漠可以建模为一个 $N \times N$ 的网格。行和列从上到下、从左到右依次编号为 $1$ 到 $N$。沙漠中的某些格子包含巫师，他们会以一种不寻常的方式帮助阿拉丁的探险。

阿拉丁在某个星期一从沙漠的左上角开始他的探险，面朝右侧。他的移动过程包括不断重复以下步骤：

1. 如果当前格子包含一个处于清醒状态的巫师，那么阿拉丁会根据巫师的指示向左或向右旋转 90 度。
2. 如果向前移动会导致阿拉丁离开沙漠，他会旋转 180 度。
3. 阿拉丁向前移动一个格子，这需要花费恰好一天的时间。

对于每个巫师，我们知道他的位置以及他一周中每一天的活动日程。日程是一个长度恰好为 7 的字符串，由字符 'L'、'R' 或 'S' 组成，每个字符表示巫师在一周中某一天（从星期一开始）的行为。字符 'L' 表示阿拉丁将被告知向左转，'R' 表示阿拉丁将被告知向右转，而 'S' 表示巫师在当天睡觉。

一个古老的预言说，在方向改变 $K$ 次（在步骤 1 和/或步骤 2 中）之后，阿拉丁就会找到黄金梨。

编写一个程序，根据古老的预言计算这次搜寻将持续多少天。

输入格式

第一行包含两个整数 $N$ 和 $K$（$2 \le N \le 200$，$1 \le K \le 1\,000\,000\,000$），分别表示沙漠的大小和预言中方向改变的次数。

第二行包含一个整数 $M$（$0 \le M \le 10\,000$），表示巫师的数量。

接下来的 $M$ 行，每行包含两个整数 $R$ 和 $C$（$1 \le R, C \le N$）以及一个由 7 个字母 'L'、'R' 或 'S' 组成的字符串。这两个数字表示巫师所在的行和列，字符串表示他的日程表。

没有两个巫师会位于同一个格子中，且 $(1, 1)$ 格子中不会有巫师。

输出格式

输出搜寻持续的天数。

子任务

对于 $50\%$ 的测试用例，$K \le 1000$。

样例

输入样例 1

3 1
0

输出样例 1

2

输入样例 2

5 2
2
1 3 RRSRRRR
1 5 RRRRLRR

输出样例 2

4

输入样例 3

5 5
3
1 3 SSRSSSS
3 3 SSSLSSS
4 3 SSRSSLS

输出样例 3

10

说明 1

在第一个样例中，阿拉丁移动了两次，到达了沙漠的边缘。然后他旋转了 180 度并找到了黄金梨。

说明 2

在第二个样例中，阿拉丁在第三天到达了第一个巫师处，但该巫师正在睡觉，因此阿拉丁继续沿相同方向前进。又过了两天，他到达了另一个巫师处，该巫师告诉他向左转。阿拉丁照做，到达了沙漠的边缘，转身并找到了黄金梨。