E. Connected Squares
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

There is an infinite grid of squares. The squares at positions $$$(0, 0)$$$ through $$$(n-1, 0)$$$ are then colored red, blue, or green. You want to color additional squares such that for each of the three colors, the subset of squares of that color is connected, where two squares are considered connected if they share an edge.

In other words, for every pair of squares of the same color $$$c$$$, it should be possible to travel from one to the other, moving only through squares of color $$$c$$$ that share an edge.

Find a solution that colors at most $$$10^6$$$ additional squares (not including the squares that are currently present), or determine that there is no solution. It can be shown that under the given constraints, if there is a solution, there is one using at most $$$10^6$$$ additional squares.

You do not need to minimize the number of additional squares.

Input

The first line of input contains a single integer $$$n$$$ ($$$1 \le n \le 100$$$) — the number of currently-colored squares.

The second and final line of input contains $$$n$$$ characters $$$\texttt{R}$$$, $$$\texttt{B}$$$, or $$$\texttt{G}$$$, where the $$$i$$$-th of these indicates the color of the square at position $$$(i-1, 0)$$$.

Output

If there is no solution, print a single integer $$$-1$$$.

Otherwise, the first line of output should contain a single integer $$$k$$$ ($$$0 \le k \le 10^6$$$) — the number of additional squares you will color.

The next $$$k$$$ lines should contain two integers $$$x$$$ and $$$y$$$, and a character $$$c$$$ ($$$-10^6 \le x, y \le 10^6$$$, $$$c \in \{\texttt{R}, \texttt{B}, \texttt{G}\}$$$) — indicating that you are adding a square with color $$$c$$$ at position $$$(x, y)$$$.

No two squares in the output should have the same coordinates, and no square in the output should have the same coordinates as any square in the input.

If there are multiple solutions, print any.

Examples
Input
7
RBGRBGR
Output
32
1 1 B
0 1 B
-1 1 B
-1 0 B
-1 -1 B
-1 -2 B
0 -2 B
1 -2 B
2 -2 B
3 -2 B
4 -2 B
4 -1 B
0 -1 R
1 -1 R
2 -1 R
3 -1 R
3 1 R
4 1 R
5 1 R
6 1 R
2 1 G
2 2 G
3 2 G
4 2 G
5 2 G
6 2 G
7 2 G
7 1 G
7 0 G
7 -1 G
6 -1 G
5 -1 G
Input
6
GBGBGB
Output
10
1 -1 B
2 -1 B
3 -1 B
4 -1 B
5 -1 B
0 1 G
1 1 G
2 1 G
3 1 G
4 1 G
Input
4
RRRB
Output
0
Note

The first test case corresponds to the image above in the statement.

Here is a visualization for the second test case:

Notice that the set of red squares is considered connected even though there are no red squares in the solution.

In the third test case, each color is already connected, so there is no need to color additional squares.