기차역 지하 통로

역에서 선로로 드나드는 길은 지하 통로 하나뿐이다. 혼잡한 시간에는 역의 한쪽에서 반대쪽으로 가려는 사람이 몰린다. 두 출구의 중요도가 비슷해서 절반쯤은 한쪽으로, 나머지 절반쯤은 반대쪽으로 걷는다. 사람은 서로를 통과하지 못하므로 서로 길을 막는다. 걷는 속도도 사람마다 달라서 빠른 사람이 앞사람을 기다리는 일이 생긴다.

통로가 많은 인원을 얼마나 잘 소화하는지 재기 위해 통로를 이차원 격자로 본다. 통로의 길이는 $l$, 너비는 $w$이고 사람 한 명은 격자점 하나를 차지한다. 선로는 무시하고, 통로의 왼쪽 면 전체와 오른쪽 면 전체가 입구다. 왼쪽 위 격자점이 $(1, 1)$, 오른쪽 아래 격자점이 $(l, w)$이며 둘 다 통로 안이다. 즉 $x$는 오른쪽으로, $y$는 아래로 커진다. 출발 위치가 서로 다른 것은 도착 시각이 서로 다르다는 뜻이다.

시간은 틱 단위로 흐른다. 속도가 $s$인 사람은 매 틱마다 자기 방향으로 $s$칸 가려 한다. 사람은 다른 사람도 벽도 통과하지 못한다. 뒷사람이 앞사람의 등에 부딪혀도 앞사람의 속도는 달라지지 않는다. 뒷사람은 앞사람 뒤에 남는 범위에서 갈 수 있는 만큼 간다. 반대 방향으로 오는 사람과 부딪히면 움직이던 사람은 부딪힌 상대의 바로 앞 격자점에서 이동을 끝낸다.

대학이 통로 오른쪽에 있어서 왼쪽에서 오른쪽으로 가는 사람이 더 급하다. 그래서 매 틱마다 오른쪽으로 가는 사람이 먼저 움직이고 그다음에 왼쪽으로 가는 사람이 움직인다. 같은 방향으로 가는 사람은 동시에 움직인다.

다른 사람과 부딪혀서 그 틱에 가려던 거리의 절반(올림) 이하만 간 사람은 짜증이 난다. 속도가 $s$인 사람이라면 실제로 간 거리가 $s$보다 작고 $\lceil s/2 \rceil$ 이하인 경우다. 짜증이 난 사람은 다음 틱이 시작되기 전에 옆으로 한 칸 비켜서려 한다.

틱 사이의 비켜서기는 다음 순서로 일어난다. 먼저 위에서 아래로, 오른쪽으로 가는 짜증 난 사람이 각자 자기 왼쪽(즉 위)으로 한 칸 비켜서려 한다. 다음으로 아래에서 위로, 왼쪽으로 가는 짜증 난 사람이 각자 자기 왼쪽(즉 아래)으로 비켜서려 한다. 다음으로 아래에서 위로, 왼쪽으로 비켜서지 못해 아직 짜증이 난 오른쪽 방향 사람이 자기 오른쪽(즉 아래)으로 비켜서려 한다. 마지막으로 위에서 아래로, 아직 짜증이 난 왼쪽 방향 사람이 자기 오른쪽(즉 위)으로 비켜서려 한다. 비켜서기는 $x$를 그대로 두고 $y$만 1 바꾸는 이동이며, 목표 격자점이 통로 안이고 비어 있을 때만 성공한다. 새 틱이 시작되면 짜증은 풀린다.

모든 사람이 통로를 떠나는 시각을 구하려 한다. 통로를 떠난다는 것은 자기가 향하던 출구 밖으로 나가는 것이다. 출발 위치에서 모든 사람이 통로 끝까지 갈 수 있는 입력만 주어진다.

첫 줄에 테스트 케이스의 개수를 나타내는 양의 정수가 주어진다. 이 값은 100 이하다. 그 뒤로 테스트 케이스마다 다음이 주어진다.

• 공백으로 구분된 정수 $l$, $w$, $p$ ($1 \le l, w \le 3000$, $1 \le p \le 1000$)가 한 줄에 주어진다. 각각 통로의 길이, 통로의 너비, 사람 수다.
• 다음 $p$개의 줄에는 공백으로 구분된 정수 $x$, $y$, $s$ ($0 < x \le l$, $0 < y \le w$, $0 < s \le 1000$)가 주어진다. 한 사람의 출발 위치 $(x, y)$와 속도 $s$다. 그 뒤에 공백 하나와 문자 하나가 이어지는데, L이면 그 사람은 통로의 왼쪽으로 걷고 R이면 오른쪽으로 걷는다.

통로를 떠난 사람은 격자에서 사라진다. $x \le 0$ 또는 $x > l$이 되면 통로를 떠난 것이다.

테스트 케이스마다 한 줄에 정수 하나를 출력한다. 모든 사람이 통로를 떠나기까지 걸린 틱 수의 최솟값이다.