위험한 교차로

ASV(Agency for Simulation of Vehicles)는 창립자 Crishna가 이끄는 기관이다. 이 기관은 국내 일부 지역 교차로에서 일어나는 차량 충돌 데이터를 얻는 프로젝트를 진행하고 있다.

첫 번째 시뮬레이션은 정해진 지역의 교차로에 차량 C대를 무작위로 배치하는 것이다. 시뮬레이션 시작 시점에 교차로마다 차량은 최대 한 대만 있다. 이 지역은 가로 차선 N개와 세로 차선 M개가 교차하는 격자이다.

시뮬레이션이 시작되면 각 차량은 처음 방향(북, 남, 동, 서)을 그대로 유지한 채 초당 교차로 한 곳의 일정한 속도로 움직인다.

같은 시각에 두 대 이상의 차량이 같은 교차로에 도착하면 그 차량들은 충돌하고 멈춘다. 이미 충돌이 일어난 교차로를 다른 차량이 지나가면, 그 차량도 멈춰 있던 차량들과 충돌한다. 이유는 알려지지 않았지만, 두 차량이 두 교차로 사이에서 가로 방향으로 충돌하면 둘 다 동쪽 교차로에서 멈추고, 세로 방향으로 충돌하면 둘 다 북쪽 교차로에서 멈춘다.

그림은 $N = 5$, $M = 6$, $C = 7$인 시뮬레이션을 보여준다. 차량은 처음 방향을 나타내는 화살표로 표시되어 있다. 강조된 차량 세 대는 어느 순간 충돌한다.

ASV 시뮬레이션 소프트웨어는 아직 완전히 신뢰할 수 없다. 그래서 초기 배치 예시를 주고, 충돌하지 않는 차량의 수를 세게 한다.

첫 줄에 정수 N, M, C가 공백으로 구분되어 주어진다. N은 가로 차선 수, M은 세로 차선 수, C는 차량 수이며 $2 ≤ N, M ≤ 10^5$, $1 ≤ C ≤ min(10^5, N × M)$을 만족한다.

이어지는 C개의 줄에는 각각 정수 $A_i$, $B_i$와 문자 D가 주어진다. 이는 i번째 차량이 $A_i$번째 가로 차선과 $B_i$번째 세로 차선이 만나는 교차로에 있고, 방향은 D라는 뜻이다. ($1 ≤ A_i ≤ N$, $1 ≤ B_i ≤ M$) D는 N(북쪽), S(남쪽), L(동쪽), O(서쪽) 중 하나이다.

한 줄에 충돌하지 않는 차량의 수를 정수로 출력한다.