Icarus GO

All submissions for this problem are available.

Icarus is super enthusiastic in becoming the best GO player in the world, and right now he is aiming to surpass his rival Troy. That is why he is training hard in many creative ways.

He knows that a great ability for a good GO player is to count the number of groups and the degrees of freedom of each one just with a quick sight.

As you know, a group is a set of stones in which each stone of the group is adjacent to another stone of the group; and the freedom degree a group is equal to the number of empty intersections that are at least adjacent to one stone in the group. In GO, adjacency is only vertical or horizontal, not diagonal. As the diagram shows, in this reduced 6x6 board there are one big white group consisting of four stones and freedom degree five (5), one black group of two stones and freedom degree four (4) and two black groups of one stone with two freedom degree two (2) each.

A good friend of him made a quick random board generator. It creates a GO board with a certain number of stones placed on it and then Icarus estimates the groups and their degrees of freedom. After that, the computer checks if he was right counting them manually. The only problem is that the computer validation has not been implemented yet, so your task is to help Icarus by writing a program that generates the correct answer. This way, Icarus will be able to validate his answers and finally defeat Troy.

Input

The first line contains a pair of integers N and S, which specify the length of the board (which is always square) and the number of stones in it. Then, S lines will follow, each one containing the following items separated by a single white space:

• A character 'B' or 'W' if the stone is black or white respectively.
• An integer C_i represents the column where the stone i is placed.
• An integer R_i represents the row where the stone i is placed.

Output

For each board you must print the string "Case #i:" in a line, where i is the board number, starting from 1. Then, you must print one line for each group in the board, printing a character 'B' if the group is black or 'W' if the group is white, the number of stones in the set and the freedom degrees of that group; those three elements should be separated by single a white space. The groups should be sorted by the following rules:

1. Put black groups before white groups.
2. If two groups are of the same color, put bigger groups first.
3. If two groups are of the same color and the same size, put groups with greater freedom degree first.

Example
Input
3
6 8
B 5 2
W 4 2
B 5 4
W 4 4
B 5 5
W 5 3
B 6 3
W 4 3
9 6
W 5 5
B 9 5
B 9 1
W 1 1
B 1 2
B 2 1
6 5
B 1 1
B 1 2
W 3 1
W 2 2
W 3 2

Output
Case #1:
B 2 4
B 1 2
B 1 2
W 4 5

Case #2:
B 1 3
B 1 2
B 1 2
B 1 2
W 1 4
W 1 0

Case #3:
B 2 2
W 3 5

Constraints:


T will be between 1 and 200, inclusive.
N will be between 1 and 106, inclusive.
S will be between 1 and min(N2,250), inclusive.
Ci will be between 1 and N, inclusive, for all i between 1 and S.
Ri will be between 1 and N, inclusive, for all i between 1 and S.
There will not be more than one stone in the same intersection.