강 건너기

건너야 할 강.

닭 Charlotte는 끊임없이 앞으로 나아가기를 좋아한다. 현재 Charlotte는 건너고 싶은 긴 강 앞에 있다. 강은 $R$개의 행과 $C$개의 열로 이루어진 격자이며, 행과 열에는 각각 $1$부터 $R$까지, 그리고 $1$부터 $C$까지 번호가 매겨져 있다. 강의 모든 칸에는 물이 차 있다. Charlotte는 현재 격자 아래쪽의 땅으로 채워진 $0$번 행에 있다.

특정 시각 $t$에 행의 시작이나 끝에서 나타나 반대편을 향해 초당 $v$칸씩 흘러가는 $1 \times 1$ 크기의 나무 조각이 $N$개 있다. 즉, 어떤 통나무는 행의 왼쪽에서 나타나 오른쪽으로 이동하고, 어떤 통나무는 오른쪽에서 나타나 왼쪽으로 이동할 수 있다. 시간은 $T=1$부터 시작하며 매초 한 번씩 이산적으로 앞으로 흐른다($T=1,2,3,\dots$).

$T=1$ 전에는 Charlotte가 어느 열의 아래쪽으로든 걸어가 전력 질주를 준비할 수 있다. Charlotte는 매우 빠른 닭이지만, 일단 달리기 시작하면 방향을 바꿀 수 없다. 또한 Charlotte는 오직 위쪽으로 곧장 달리고 싶어 한다. 따라서 Charlotte는 궁금해한다. 어느 순간에 $R \times C$ 강 내부의 어떤 열에서 그 열의 모든 행마다 통나무가 존재할 수 있을까?

채점

여러 테스트 그룹으로 해답을 검사한다. 한 그룹의 점수를 얻으려면 그 그룹의 모든 테스트 케이스를 통과해야 한다.

그룹 | 점수 | 제약 조건

$1$ |$10$| $N \leq 500$, $C, t \leq 2000$

$2$ |$15$| $N, C, t \leq 2000$

$3$ |$25$| $N \leq 2000$

$4$ |$25$| $N \leq 20{,}000$

$5$ |$25$| 추가 제약 조건 없음.

입력의 첫 번째 줄에는 정수 $R$, $C$, $N$이 주어진다($R=1000$, $1 \leq C \leq 10^9$, $1 \leq N \leq 10^5$). 이들은 각각 격자의 행 수와 열 수, 통나무의 수이다.

이어지는 $N$개의 줄은 각각 하나의 통나무를 설명한다. 각 줄에는 정수 $r$, $t$, $v$와 문자 $s$가 주어진다($1 \leq r \leq R$, $1 \leq t \leq 10^9$, $1 \leq v \leq C$, $s \in \{\texttt{L}, \texttt{R}\}$). 이는 시각 $t$에 $r$번 행의 $s$ 쪽에서 통나무가 나타나며(L는 왼쪽에서, R는 오른쪽에서 나타남을 뜻한다), 초당 $v$칸의 속도로 출발한 쪽의 반대편을 향해 이동한다는 뜻이다. 형식적으로, $s=$L이면 $1$번 열에서 시작하고, $s=$R이면 $C$번 열에서 시작한다.

통나무끼리 상호 작용하는 것은 완전히 무시해야 한다. 같은 행에서 통나무가 다른 통나무를 추월할 수도 있고, 서로 다른 방향으로 가는 두 통나무가 서로 교차할 수도 있으며, 어느 순간에는 같은 칸에 여러 통나무가 있을 수도 있다.

참고: 예제를 제외한 모든 테스트 케이스에서는 $R=1000$이다. 예제는 편의를 위해 더 작게 주어졌을 뿐이다.

YES을 출력하고, 다음 줄에는 강 내부의 어떤 열에서 그 열의 모든 행에 통나무가 존재하는 시각 $T$를 출력한다. $T$는 양의 정수여야 한다. 유효한 $T$가 여러 개라면 그중 아무거나 출력해도 정답으로 인정된다. 유효한 $T$가 존재한다면 $64$비트 부호 있는 정수로 나타낼 수 있음이 증명되어 있다. 그러한 시각 $T$가 존재하지 않으면 NO을 출력한다.

참고: 쉽게 볼 수 있도록 모든 예제에서는 $R \neq 1000$이다. 따라서 이 문제에서 만점을 받기 위해 이 테스트 케이스들을 해결할 필요는 없다. 점수를 부여하는 모든 테스트 케이스에서는 $R=1000$이다. 그래도 제출한 해답이 예제를 올바르게 해결하는지에 대한 피드백은 제공된다.

예제 $1$에서는 시각 $1$에 통나무가 있다. $R=1$이므로 Charlotte는 시각 $1$에 이 통나무를 이용해 강을 건널 수 있다.

예제 $2$은 아래에 시각화되어 있다. 화살표는 각 통나무가 이동하는 방향을 나타낸다.

[h]

[h]

두 통나무가 시각 $T=2$에 나란히 정렬되므로 답은 YES이다.

예제 $3$에서는 두 통나무가 격자 내부에서 한 번도 나란히 정렬되지 않는다. 따라서 답은 NO이다.