Under construction

Still being built. Things may change

Aladdin and the Lamp

Time limit1sMemory limit128 MB

Summary
Simulate a grid walker whose turns depend on cell wizards and day of week, and find the day count when exactly K direction changes have occurred, using cycle detection since K can reach one billion.
Level

Medium7 of 10

Topics
Simulation, Math, Implementation
Solved
No attempts yet

Problem

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.

Input

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).

Output

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

Examples3

  1. Example 1

    Input
    3 1
0
    Expected output
    2

  2. Example 2

    Input
    5 2
2
1 3 RRSRRRR
1 5 RRRRLRR
    Expected output
    4

  3. Example 3

    Input
    5 5
3
1 3 SSRSSSS
3 3 SSSLSSS
4 3 SSRSSLS
    Expected output
    10