Stealth Ninja

A large palace contains a hall whose floor is a $(2n-1) \times (2n-1)$ grid of squares. The rows are numbered from $1$ to $2n-1$ from the front of the hall to the back, and the columns are numbered from $1$ to $2n-1$ from the left to the right.

Every square that lies on both an even-numbered row and an even-numbered column is occupied by a square wooden support column; all other squares are empty. As a result the empty squares form $n$ corridors running left-to-right (along the odd-numbered rows) and $n$ corridors running front-to-back (along the odd-numbered columns). Each front-to-back corridor ends, at the front wall and at the back wall, in a door opening covered by a curtain. Every other part of the walls is closed.

The hall is guarded by $k$ guards. Each guard stands at a crossing of a front-to-back corridor and a left-to-right corridor, that is, on a square whose row and column are both odd. A guard spends $4$ seconds looking toward the left of the hall, then $4$ seconds toward the back, then $4$ seconds toward the right, then $4$ seconds toward the front, and repeats this $16$-second cycle forever. The guards are not necessarily synchronized: at time $0$ each guard may already be looking in any of the four directions. While a guard looks in a given direction it sees every square along its corridor in that direction, all the way to the wall. Guards can see past one another, but they cannot see through a curtain.

A ninja wants to cross the hall from the front to the back without meeting a guard and without ever being seen. Before entering, the ninja waits in row $0$, that is, behind one of the curtains in the front wall; it chooses which curtain and how long to wait. It may leave through any curtain in the back wall. Walking from one square to an orthogonally adjacent square takes the ninja $2$ seconds, and while walking it would be seen by any guard that, at any moment during that step, is looking at the square it is leaving or the square it is entering. The ninja may never stand on a square that a guard is currently watching, and may never enter a square occupied by a guard or a wooden column.

As an example, take $n = 4$ with the five guards of the sample case. The ninja can cross as follows. It first waits. After $8$ seconds the guard in row $5$, column $1$ turns to look left, and the ninja steps through the curtain in column $1$. After $10$ seconds it reaches row $1$, column $1$; after $12$ seconds it reaches row $2$, column $1$. It waits there until the guard in row $3$, column $5$ turns to look toward the back, then walks on and disappears behind the curtain in column $3$ just before the guard in row $1$ turns to look in that direction. In this way the ninja succeeds.

For each hall, determine whether the ninja can cross successfully.

The first line contains a single integer: the number of test cases. Each test case has the following format:

• One line with two integers $n$ and $k$: the number of corridors in each direction ($1 \le n \le 250$) and the number of guards ($0 \le k \le 500$).
• $k$ lines, one per guard. Each line contains an odd integer $r$ ($1 \le r \le 2n-1$), an odd integer $c$ ($1 \le c \le 2n-1$), and one of the letters L, B, R, or F. Here $r$ and $c$ are the row and column of the guard, and the letter is the direction it is looking at time $0$ (left, back, right, or front).

No two guards share the same position.

For each test case, print a single line containing either succeeds or fails.

In the sample case ($n = 4$ with five guards) the ninja can cross the hall from front to back without being seen, so the answer is succeeds. This is the situation described in the worked example above.