Пофарбування огорожі
Мер міста Многоярославця вирішив побудувати перед своїм будинком огорожу з n дерев'яних дощок і найняти кращого маляра міста для його пофарбування. Оскільки забор повинен стати головною історичною пам'яткою міста, кращий дизайнер міста для кожної дошки призначив ретельно вибраний колір, у який вона повинна бути пофарбована.
Для пофарбування головний маляр вирішив застосувати новітню технологію, спеціально розроблену ним для виконання цього завдання. Пофарбуванням огорожі буде займатись спеціальний робот, який за одну годину може пофарбувати довільно вибраний відрізок огорожі (набір сусідніх дощок) у деякий колір. Оскільки завдання повинно бути виконано якомога швидше, потрібно скласти програму для робота, яка дозволить досягнути потрібного розфарбування за мінімальний час. Залишити яку-небудь з дощок непофарбованою, звичайно, заборонено.
Вхідні дані
У першому рядку вхідного файлу записано число n (1 ≤ n ≤ 300), де n - кількість дощок в огорожі. Другий рядок містить рядок з n символів, які описують потрібне пофарбування огорожі. Кольори позначаються великими латинськими буквами.
Вихідні дані
У перший рядок вихідного файлу виведіть m - найменший можливий час пофарбування огорожі в годинах. Наступні m рядків повинні містити програму пофарбування для робота. Кожен рядок повинен містити два числа l_{i та}_{ }r_i, а також велику букву латинського алфавіту, яка задає колір c_i і означає, що робот повинен пофарбувати ділянку огорожі з l_i-ї по r_i-ту дошку у колір c_i (якщо довжина огорожі n, повинно виконуватись 1 ≤ l_i ≤ r_i ≤ n).