Покраска забора#4151

Покраска забора

1 секунда

64 мегабайта

Medium

Мэр Многоярославца решил построить забор перед своим домом из $n$ деревянных досок и нанял лучшего маляра города, чтобы его покрасить. Поскольку забор должен стать основной достопримечательностью города, лучший дизайнер города назначил тщательно подобранный цвет для каждой доски.

Для выполнения задачи главный маляр решил использовать передовую технологию, разработанную специально для этой работы. Особый робот за одну минуту покрасит любой выбранный отрезок забора (набор последовательных досок) в выбранный цвет. Чтобы выполнить работу как можно быстрее, вам нужно составить программу для робота, которая позволит добиться необходимой окраски за минимальное количество часов. Естественно, нельзя оставить ни одной доски неокрашенной.

Input

В первой строке задано число $n$ ( $1 \leq n \leq 300$ 1 \le n \le 300) — количество досок в заборе. Во второй строке содержится строка из $n$ символов, описывающая требуемую окраску забора. Цвета обозначаются заглавными буквами латинского алфавита.

Output

В первой строке выведите $m$ — минимальное количество часов, необходимое для покраски забора. В последующих $m$ строках опишите программу покраски для робота. В каждой строке укажите два целых числа $l_{i}$ l_i и $r_{i}$ r_i и заглавную латинскую букву $c_{i}$ c_i, что означает: робот должен покрасить сегмент забора с $l_{i}$ l_i-й по $r_{i}$ r_i-ю доску включительно цветом $c_{i}$ c_i. Требуется, чтобы $1 \leq l_{i} \leq r_{i} \leq n$ 1 \le l_i \le r_i \le n.

Examples

Example 1