Aladdin's Golden Pear Quest

Aladdin is searching for the Golden Pear in a vast desert represented as an \(n\times n\) grid. The rows and columns are numbered from 1 to \(n\) (top‐to‐bottom and left‐to‐right respectively). In the desert there are \(m\) wizards, each positioned in a grid cell. Every wizard has a weekly schedule given by a string of 7 characters (each being L, R or S) corresponding to the days Monday through Sunday. A character of L means that on that day the wizard, if awake, instructs Aladdin to turn left (\(90^\circ\)); R instructs him to turn right (\(90^\circ\)); and S means the wizard is sleeping.

Aladdin starts his adventure on Monday at the top‐left cell, \((1, 1)\), and is initially facing right (east). Every day he repeats the following steps:

1. If there is a wizard in his current cell and the wizard is awake (i.e. the schedule character for that day is L or R), he turns accordingly. Turning left means a \(90^\circ\) turn counterclockwise and turning right means a \(90^\circ\) turn clockwise.
2. If moving forward in his current direction would take him out of the desert, he turns \(180^\circ\). This counts as an additional turn.
3. Aladdin then moves one cell forward in his current direction, which takes one day.

An ancient prophecy foretells that immediately after Aladdin changes direction a total of \(k\) times (whether due to a wizard’s instruction or because he turns when facing the desert boundary), he will find the Golden Pear. Write a program to determine how many days Aladdin’s adventure lasts (i.e. the number of days completed before he finds the Golden Pear).

Note: If a turn that makes the total number of turns equal to \(k\) occurs during step 1 or step 2, the adventure ends immediately without completing the movement step of that day.

inputFormat

The first line contains three integers \(n\), \(m\), and \(k\) \((1 \leq n \leq 10^3, \; 0 \leq m \leq n^2, \; 1 \leq k \leq 10^6)\).

Then \(m\) lines follow. Each of these lines contains two integers \(r\) and \(c\) \((1 \leq r, c \leq n)\) and a string of 7 characters representing the wizard's weekly schedule starting from Monday. The characters in the schedule are all either L, R, or S.

If a cell does not contain any wizard, no instruction is given in that cell.

outputFormat

Output a single integer representing the number of days Aladdin’s adventure lasts before he finds the Golden Pear.

sample

5 1 1
1 1 RRSRRSS

0