Description

The desert that Aladdin is searching can be viewed as an $n \times n$ grid. Rows and columns are numbered from $1$ to $n$ from top to bottom and from left to right. There are $m$ wizards in some cells of the desert grid, and they help Aladdin in an unusual way.

On Monday, Aladdin starts his quest at the top-left corner $(1,1)$, facing right. His actions consist of repeating these steps:

1. If there is an awake wizard in the current cell, then Aladdin turns $90$ degrees left or right according to what the wizard says.
2. If moving forward would take Aladdin out of the desert, he turns $180$ degrees.
3. Aladdin moves forward by one cell, which takes one day.

For each wizard, we know his position and his activity plan for each day of the week. Each wizard’s schedule is a string of seven letters (only L, R, or S), where each character tells what the wizard does on a day of the week (starting from Monday). The letter L means that on that day Aladdin will be told to turn left, R means he will be told to turn right, and S means the wizard is sleeping that day.

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

Input Format

The input contains $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 prophecy.
The second line contains an integer $m$, representing the number of wizards.
The next $m$ lines each contain two integers and a string. The $i$-th of these lines gives the wizard’s row, column, and a one-week schedule (starting from Monday).

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

Output Format

Output one line containing one integer, representing the number of days the adventure lasts.

3 1
0

2

5 2
2
1 3 RRSRRRR
1 5 RRRRLRR

4

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

10

Hint

[Sample 1 Explanation]

For sample $1$, after moving two cells, Aladdin reaches the edge of the desert. Then he turns $180$ degrees and finds the Golden Pear. Therefore, the adventure lasts $2$ days.

[Sample 2 Explanation]

For sample $2$, Aladdin finds the first wizard after walking for two days, but the wizard is sleeping at that time, so Aladdin keeps walking for two more days. Then on day $4$ he finds the second wizard, who tells him to turn left. Aladdin does so, then he reaches the edge of the desert, turns $180$ degrees, and finds the Golden Pear. Therefore, the adventure lasts $4$ days.

[Constraints]

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

[Source]

This problem is from COCI 2008-2009 CONTEST 5 T6 KRUSKA, using the original testdata settings, with a full score of $130$ points.

Translated and compiled by Eason_AC.

Translated by ChatGPT 5