H. Packing Cupcakes
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Strawberry Shortcake is packing cupcakes for her friend Blueberry Tallcake. Shortcake has three different flavors of cupcakes: strawberry, blueberry, and pineberry. She has a $$$N \times M$$$ dimension cupcake container, initially empty, and will place cupcakes into empty spots one-by-one until the container is full.

As Shortcake places cupcakes into the container, she observes the formation of regions of the same cupcake flavor. She formally defines a single 'region' as a maximal connected group of cupcakes of the same flavor, where two cupcakes are considered connected if they are orthogonally adjacent to each other or there is a chain of adjacent cupcakes from one to the other. Shortcake is curious and wonders how many distinct regions exist in the container after each cupcake is placed.

Input

The first line of input contains $$$N,\ M,\ (1 \leq N, M \leq 300)$$$, the number of rows and columns in the cupcake container.

The next $$$N \times M$$$ lines each contain $$$i,\ j,\ f\ (1 \leq i \leq N,\ 1 \leq j \leq M)$$$ meaning Shortcake places a cupcake of flavor $$$f = $$$ S, B, or P (strawberry, blueberry, or pineberry) at position $$$(i, j)$$$ in the container.

Output

For each cupcake that Shortcake places, output the number of distinct regions that exist in the container after she places the cupcake.

Examples
Input
2 2
2 1 P
1 2 P
2 2 S
1 1 P
Output
1
2
3
2
Input
2 3
1 3 S
1 2 P
1 1 P
2 1 P
2 2 B
2 3 B
Output
1
2
2
2
3
3
Input
3 3
2 3 B
3 1 P
3 2 S
1 1 B
3 3 S
1 2 B
1 3 B
2 2 P
2 1 P
Output
1
2
3
4
4
4
3
4
3
Note