Problem Background

Aladdin has grown tired of palace life. He has a stable job, his wife Jasmine and children are on the road, and life has become monotonous. Driven by all this, he decided to embark on one last adventure before settling down. He decided to find the Golden Pear, a highly precious legendary artifact that has never been found by anyone.

Problem Description

The desert Aladdin is searching in can be considered as an $n \times n$ grid. Rows and columns are numbered from $1$ to $n$ from top to bottom and from left to right, respectively. There are $m$ wizards in the grid of the desert, who help Aladdin complete his task in an unusual way.

Aladdin starts his task on Monday at the top-left corner $(1,1)$ and faces right. His actions include repeating these steps:

1. If there is a awake wizard in the current grid, Aladdin will turn $90$ degrees left or right according to the wizard's instruction.
2. If moving forward would take Aladdin out of the desert, he will turn $180$ degrees.
3. Aladdin moves one grid forward, which takes him one day.

For each wizard, we know their position and their weekly activity schedule. Each wizard's schedule is a string of seven letters (containing only L, R, or S), each telling what the wizard does on a particular day of the week (starting from Monday). The letter L means Aladdin will be told to turn left on that day, R means he will be told to turn right, and S means the wizard is asleep that day.

An ancient prophecy says that after changing direction $k$ times (through steps $1$ and $2$), Aladdin will find the Golden Pear. According to this ancient prophecy, write a program to calculate how many days the adventure will last.

Input Format

The input consists of $m+2$ lines.

The first line contains two integers $n, k$, representing the side length of the desert and the number of direction changes mentioned in the ancient prophecy, respectively.
The second line contains an integer $m$, representing the number of wizards.
The following $m$ lines, the $i$-th line contains two integers and a string, representing the wizard's row coordinate, column coordinate, and their weekly actions (starting from Monday).

It is guaranteed that there is no wizard at $(1,1)$, no two wizards in the same grid, and no wizard outside the desert.

Output Format

The output consists of one line, an integer representing the number of days the adventure will last.

Sample Input and Output

Sample Input #1

3 1
0

Sample Output #1

2

Sample Input #2

5 2
2
1 3 RRSRRRR
1 5 RRRRLRR

Sample Output #2

4

Sample Input #3

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

Sample Output #3

10

Notes

[Sample 1 Explanation]

For Sample $1$, after moving two grids, Aladdin reaches the edge of the desert, then he turns $180$ degrees and finds the Golden Pear. So the adventure will last $2$ days.

[Sample 2 Explanation]

For Sample $2$, after walking for two days, Aladdin finds the first wizard, but this wizard is asleep, so Aladdin continues for two more days. On the fourth day, he finds the second wizard, who tells him to turn left, and Aladdin does so. Then he reaches the edge of the desert, turns $180$ degrees, and finds the Golden Pear. So the adventure will last $4$ days.

[Data Range]

For $50\%$ of the data, it is guaranteed that $k \leq 1000$.
For all data, $2 \leq n \leq 200$, $1 \leq k \leq 10^9$, $0 \leq m \leq 10^4$.

[Problem Source]

This problem is from COCI 2008-2009 CONTEST 5 T6 KRUSKA, configured according to the original problem data, with a full score of $130$ points.

Provided by Eason_AC for translation and arrangement.

见题面 Input 部分

见题面 Output 部分