Aladdin and the Lamp

Aladdin has grown tired of his quiet life in the palace. He decides to leave on an adventure to find a legendary lamp said to be buried somewhere in the desert.

The desert is an N by N grid. Rows are numbered from top to bottom, and columns are numbered from left to right, both starting at 1. Some cells contain wizards. When Aladdin is in such a cell, the wizard may tell him to turn.

Aladdin starts in the top-left cell, (1, 1). It is Monday, and he is initially facing right. Each day he moves to the next cell by performing the following steps in order.

1. If the wizard in Aladdin's current cell is awake that day, Aladdin turns in the direction the wizard says.
2. If moving one cell forward would leave the desert, Aladdin turns 180 degrees.
3. Aladdin moves one cell forward. This movement takes exactly one day; the first two steps take no time.

Each wizard's instructions depend on the weekday and are given as a string of length 7. The characters correspond to Monday, Tuesday, ..., Sunday. L means turn 90 degrees left, R means turn 90 degrees right, and S means the wizard is asleep that day.

A famous prophet said that Aladdin will find the lamp when he has changed direction exactly K times in steps 1 and 2. Determine how many days have elapsed when this happens.

The first line contains the desert size N and the prophet's number K. (2 <= N <= 200, 1 <= K <= 1,000,000,000)

The second line contains the number of wizards M. (0 <= M <= 10000)

Each of the next M lines contains a wizard's row R, column C, and schedule string. R is the row number and C is the column number.

No cell contains more than one wizard, and there is never a wizard at (1, 1).

Print the total number of days elapsed when Aladdin finds the lamp.