Painting the Fence
The mayor of Mnogoyaroslavets has decided to construct a fence in front of his house using n wooden planks and has hired the city's top painter to paint it. As the fence is intended to become a key historical landmark, the city's leading designer has meticulously chosen a specific color for each plank.
To accomplish this, the chief painter will employ cutting-edge technology he developed specifically for this project. A specialized robot will paint any selected segment of the fence (a series of consecutive planks) in a chosen color within one hour. To ensure the task is completed as swiftly as possible, a program must be created for the robot to achieve the desired painting in the minimum time. Naturally, leaving any plank unpainted is not an option.
Input
The first line of the input file contains the number n (1 ≤ n ≤ 300), representing the number of planks in the fence. The second line contains a string of n characters that specifies the desired color for each plank. Colors are represented by uppercase Latin letters.
Output
On the first line of the output file, print m - the minimum number of hours required to paint the fence. The following m lines should detail the painting program for the robot. Each line should include two numbers l_i and r_i, along with a capital Latin letter indicating the color c_i. This means the robot should paint the section of the fence from the l_i-th to the r_i-th plank with color c_i (ensuring that for a fence of length n, 1 ≤ l_i ≤ r_i ≤ n).