Langton's Ants

Langton's Ant is a game played on an infinite grid of squares with a few simple rules. At the beginning of the simulation the every square of the grid is colored white, and an ant is placed onto the grid, facing in some direction Up, Down, Left, or Right. On every turn, the ant then makes a decision:

• If the ant is on a white square, it turns 90° clockwise, changes the square to black, then moves forward 1 space.
• If the ant is on a black square, it turns 90° counter-clockwise, changes the square to white, then moves forward 1 space.

If an ant begins at the coordinates (0, 0) facing Up on turn 0, he will take the following path:

 Turn │ Column │ Row │ Direction │ Square Color 
──────│────────│─────│───────────│────────────── 
   0  │    0   │  0  │   Up      │    White      
   1  │    1   │  0  │   Right   │    White      
   2  │    1   │ -1  │   Down    │    White      
   3  │    0   │ -1  │   Left    │    White      
   4  │    0   │  0  │   Up      │    Black      
   5  │   -1   │  0  │   Left    │    White      
   6  │   -1   │  1  │   Up      │    White      
   7  │    0   │  1  │   Right   │    White      
   8  │    0   │  0  │   Down    │    White      
   9  │   -1   │  0  │   Left    │    Black      
  10  │   -1   │ -1  │   Down    │    White      
  11  │   -2   │ -1  │   Left    │    White      

The path of the ant described above, shown for many more turns.

Let's add a little variation to this idea by allowing multiple ants to exist on the board at once. We'll need to make a few more clarifications to the original ruleset:

• All ants make decisions and move simultaneously.
• Multiple ants may occupy on any given square on the same turn.
• When multiple ants leave a square, the square will only change color once. Squares cannot be inverted multiple times per turn.

Problem Statement

Input Data
First line is Q, the quantity of testcases.
Each testcase will begin with a line of two space-separated integers N A, where Nis the quantity of turns to simulate the game for, and A is the quantity of ants on the board.
A lines will then follow, each with three space-separated values x y dir, being the initial column, row, and direction of each ant. Note that dir will be a single capital letter corresponding to a direction.

Answer
Should be Q space-separated integers, corresponding to quantity of black squares showing on the gird after each simulation.

Example

input data:
4
10 1
0 0 U
10 2
0 0 U
3 0 U
10 2
0 0 U
2 0 U
3210 4
0 1 U
1 2 D
2 3 L
3 0 R

answer:
7 14 8 561