알라딘과 램프

알라딘은 궁전의 반복되는 생활에 싫증을 느끼고, 사막 어딘가에 묻혀 있다는 전설의 램프를 찾기 위해 모험을 떠나기로 했다.

사막은 N행 N열 격자로 나타낼 수 있다. 행은 위에서 아래로, 열은 왼쪽에서 오른쪽으로 1번부터 번호가 붙어 있다. 몇몇 칸에는 마법사가 살고 있으며, 알라딘이 그 칸에 있을 때 마법사는 알라딘에게 방향을 바꾸라고 알려줄 수 있다.

알라딘은 가장 왼쪽 위 칸 (1, 1)에서 출발한다. 출발하는 날은 월요일이고, 처음에는 오른쪽을 바라보고 있다. 알라딘은 매일 다음 과정을 순서대로 수행해 다음 칸으로 이동한다.

1. 현재 칸에 있는 마법사가 그날 깨어 있다면, 알라딘은 마법사가 말한 방향으로 돈다.
2. 현재 바라보는 방향으로 한 칸 전진하면 사막 밖으로 나가게 된다면, 알라딘은 180도 방향을 바꾼다.
3. 알라딘은 한 칸 전진한다. 이 이동에는 정확히 하루가 걸리고, 앞의 두 과정에는 시간이 걸리지 않는다.

각 마법사의 지시는 요일에 따라 달라지며, 길이 7의 문자열로 주어진다. 문자는 월요일, 화요일, ..., 일요일에 대응한다. L은 왼쪽으로 90도, R은 오른쪽으로 90도 방향을 바꾸라는 뜻이고, S는 그날 마법사가 잠들어 있다는 뜻이다.

유명한 예언자는 알라딘이 1번과 2번 과정에서 방향을 정확히 K번 바꾸면 램프를 발견한다고 말했다. 이때 램프를 발견하기까지 며칠이 지났는지 구하시오.

첫째 줄에 사막의 크기 N과 예언자가 말한 수 K가 주어진다. (2 <= N <= 200, 1 <= K <= 1,000,000,000)

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

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

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

알라딘이 램프를 발견하기까지 걸린 총 일수를 출력한다.