시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 4 2 2 66.667%

문제

알라딘은 궁전에서 지루한 삶에 싫증을 느꼈다. 항상 변함없이 똑같은 일과 부인 자스민과 아이들은 알라딘에게 더 이상 큰 흥미를 가져다주지 못했다. 그는, 더 이상 궁전에서 지루한 삶을 살 수 없다고 생각했고 모험을 떠나기로 했다.

알라딘이 살고있는 나라에는 요정이 나타나는 램프가 묻혀있다는 전설이 있다. 이 램프는 지금까지 그 누구도 찾지 못했던 램프이다. 알라딘은 이 램프를 찾기로 했다.

예로부터 내려오는 전설에 의하면 램프는 사막에 묻혀있다. 사막은 N*N 칸이 그리드형태로 배열되어 있는 모습으로 나타낼 수 있다. 행과 열은 위에서 부터 아래로, 왼쪽부터 오른쪽으로 1번부터 N번까지 번호가 매겨져 있다. 어떤 칸에는 마법사가 살고 있고, 마법사는 알라딘에게 가야할 방향을 알려준다.

알라딘은 사막의 가장 왼쪽 위 칸에서 모험을 시작한다. 이 날은 월요일이며, 알라딘은 오른쪽을 보고 있다. 알라딘은 아래 세 단계를 거쳐서 다음 칸으로 이동하게 된다.

1. 알라딘이 있는 칸에 마법사가 깨어있다면, 알라딘은 마법사가 말해주는 방향으로 방향을 바꾼다. 이 때, 마법사가 말하는 방향은 90도 왼쪽 방향과 오른족 방향 둘 중 하나이다.

2. 알라딘이 한 칸 전진했을 때, 사막읙 경계를 벗어난다면, 그는 180도 방향을 바꾼다.

3. 알라딘은 한 칸 전진하고, 이것은 정확하게 하루가 걸린다. (1, 2단계에 걸리는 시간은 없다)

모든 마법사가 말해주는 방향은 요일에 따라서 다르고, 길이가 7인 문자열로 나타낼 수 있다. 문자열은 'L', 'R', 'S'로 이루어져 있으며, 각 문자는 어떤 요일에 무슨 방향을 말해주는지를 나타낸다. 첫 번째 문자는 월요일, 두 번째 문자는 화요일, ... 이며, 'L'은 왼쪽으로, 'R'은 오른쪽으로 방향을 바꾸라는 의미이다. 'S'는 그 날은 마법사가 잠을 잔다는 뜻이다.

알라딘은 모험을 떠나기전에 유명한 예언가는 알라딘이 방향을 K번 바꾼다면 (1단계와 2단계) 램프를 발견한다고 말했다. 이 예언대로라면 알라딘은 몇 일 만에 램프를 발견하는지 구하는 프로그램을 작성하시오.

입력

첫째 줄에 사막의 크기 N과 예언가의 예언 K가 주어진다. (2 ≤ N ≤ 200, 1 ≤ K ≤ 1,000,000,000)

둘째 줄에는 마법사의 수 M이 주어진다. (0 ≤ M ≤ 10000)

다음 M개 줄에는 마법사의 위치 R, C와 스케쥴을 나타내는 문자열이 주어진다. R은 마법사가 있는 행의 번호, C는 열의 번호이다.

한 칸에 두 명 이상의 마법사가 있는 경우는 없으며, 항상 (1, 1)에는 마법사가 없다.

출력

첫째 줄에 램프를 발견하는데 총 몇 일이 걸리는지 출력한다.

예제 입력

5 2
2
1 3 RRSRRRR
1 5 RRRRLRR

예제 출력

4

힌트