Train Station Tunnel

At the station there is only one way to get on or off the tracks: a single pedestrian tunnel. During rush hour it fills with people who want to get from one side of the station to the other. The two exits matter about equally, so roughly half the people walk one way and the other half walk the other way. People cannot walk through each other, so they get in each other's way. They also walk at different speeds, so a fast person sometimes has to wait behind a slower one.

To measure how well the tunnel handles a large crowd, model it as a two dimensional grid. The tunnel has length $l$ and width $w$, and each person takes up exactly one grid point. Ignore the tracks: the whole left side and the whole right side of the tunnel are entrances. The top left grid point is $(1, 1)$ and the bottom right grid point is $(l, w)$, and both are inside the tunnel. So $x$ grows to the right and $y$ grows downwards. Different starting positions represent different arrival times.

Time passes in ticks. A person with speed $s$ tries to walk $s$ grid points in her own direction during every tick. Nobody can walk through another person or through a wall. If a person walks into the back of another person, the speed of the person in front does not change: the person behind walks as far as she can while staying behind the person in front. If a person walks into someone coming the other way, she ends her move on the grid point directly in front of the person she walked into.

The university is on the right side of the tunnel, so the people walking from left to right are in more of a hurry. During every tick the people walking to the right move first, and the people walking to the left move after them. People walking in the same direction move at the same time.

A person who walked into another person and covered at most half the distance she wanted to cover in that tick, rounded up, becomes annoyed. For speed $s$ that means she walked fewer than $s$ grid points and at most $\lceil s/2 \rceil$ of them. An annoyed person tries to step to one side before the next tick starts.

The steps between two ticks happen in this order. First, from top to bottom, every annoyed person walking right tries to step to her left, which is up. Then, from bottom to top, every annoyed person walking left tries to step to her left, which is down. Then, from bottom to top, every person walking right who is still annoyed because she could not step left tries to step to her right, which is down. Finally, from top to bottom, every person walking left who is still annoyed tries to step to her right, which is up. A step keeps $x$ and changes $y$ by one, and it succeeds only when the target grid point is inside the tunnel and empty. Nobody is annoyed any more once a new tick starts.

Find the time at which every person has left the tunnel, that is, has passed the exit she was walking towards. Every input lets all people reach the end of the tunnel from their starting positions.

The first line holds one positive integer, the number of test cases, which is at most 100. Each test case follows in this form.

• One line with three space separated integers $l$, $w$ and $p$ ($1 \le l, w \le 3000$, $1 \le p \le 1000$): the length of the tunnel, the width of the tunnel and the number of people.
• $p$ lines, each with three space separated integers $x$, $y$ and $s$ ($0 < x \le l$, $0 < y \le w$, $0 < s \le 1000$): the starting position $(x, y)$ and the speed $s$ of one person. A space and a single character follow. L means that the person walks towards the left side of the tunnel and R means that she walks towards the right side.

A person who exits the tunnel is removed from the grid. A person exits the tunnel at $x \le 0$ or at $x > l$.

For each test case, print one line with a single integer: the smallest number of ticks after which every person has left the tunnel.