Пофарбування огорожі#4151
Мер Многоярославця вирішив побудувати паркан перед своїм будинком, використовуючи дерев’яних дощок, і найняв найкращого міського маляра, щоб його пофарбувати. Оскільки паркан має стати головною пам’яткою міста, найкращий міський дизайнер призначив ретельно обраний колір для кожної дошки.
Для виконання цієї роботи головний маляр вирішив застосувати передову технологію, розроблену спеціально для цієї мети. Спеціальний робот може за одну годину пофарбувати у вибраний колір будь-який виділений сегмент паркану (набір послідовних дощок). Щоб виконати завдання якнайшвидше, слід скласти програму для робота, яка дозволить досягнути бажаного фарбування за мінімальну кількість годин. Звичайно, не можна залишати жодної дошки непофарбованою.
У першому рядку задано число (1 \le n \le 300) — кількість дощок у паркані. У другому рядку міститься рядок з символів, що описує бажане фарбування паркану. Кольори позначаються великими латинськими літерами.
У першому рядку виведіть — мінімальну кількість годин, необхідну для фарбування паркану. У наступних рядках опишіть програму фарбування для робота. У кожному рядку повинно бути два цілі числа l_i та r_i, і велика латинська літера c_i, що означає: робот має пофарбувати сегмент паркану з l_i-ої по r_i-у дошку включно у колір c_i. Необхідно, щоб 1 \le l_i \le r_i \le n.
Приклад 1