There is a convex polygon with vertices painted in three colors: Red (R), Green (G) and Blue (B). It is known that all the colors are present and any two neighbor vertices have different colors. You are to find out whether it is possible to cut this polygon with noncrossing diagonals so that each of the obtained triangles would have all vertices of different colors: one red, one green and one blue vertex.
Point out a possible way of the cutting if the cutting is possible.
Input
The first line contains a number N of the polygon vertices (4 ≤ N ≤ 1000). There are N symbols of the set {'R', 'G', 'B'} in the second line that specify a color for the correspondent vertex.
Output
The first line should contain either a number of drawn diagonals in case the required cutting is possible or the number 0 otherwise (cutting is impossible). In the first case the following lines should contain a description of the drawn diagonals. The description of a diagonal takes one line and consists of diagonal vertices numbers. The numbers are separated with a space.
If there are several possible cuttings that satisfy the requirements you may output any of them.
Sample
input | output |
---|
7
RBGBRGB
| 4
1 3
3 7
5 7
5 3
|
Problem Author: Dmitry Filimonenkov
Problem Source: Third USU personal programming contest, Ekaterinburg, Russia, February 16, 2002