Painting the Fence#4151
The mayor of Mnogoyaroslavets decided to build a fence in front of his house using wooden planks and hired the city's best painter to paint it. Since the fence is intended to become the city's principal landmark, the city's best designer assigned a carefully chosen color for each plank.
To carry out the task, the chief painter decided to use cutting-edge technology developed specifically for the job. A special robot will paint any selected segment of the fence (a set of consecutive planks) in a chosen color in one hour. To complete the job as quickly as possible, you should compose a program for the robot that allows it to achieve the desired coloring in the minimal number of hours. Naturally, it is prohibited to leave any plank unpainted.
The first line contains the number (1 \le n \le 300), the number of planks in the fence. The second line contains a string of characters, describing the required coloring of the fence. Colors are denoted by uppercase Latin letters.
In the first line, output — the minimum number of hours required to paint the fence. The following lines should describe the painting program for the robot. Each line should contain two integers l_i and r_i, and an uppercase Latin character c_i, meaning the robot must paint the segment of the fence from the l_i-th to the r_i-th plank with color c_i. It is required that 1 \le l_i \le r_i \le n.
Example 1