Çəpərin boyanması
Şəhər Mnogoyaroslavetsin meri, evinin qarşısında n taxta lövhədən ibarət bir hasar tikib rəngləmək üçün şəhərin ən yaxşı rəssamını işə götürmək qərarına gəldi. Bu hasar şəhərin əsas tarixi abidəsi olacağı üçün, şəhərin ən yaxşı dizayneri hər bir lövhə üçün xüsusi bir rəng seçdi və həmin lövhə həmin rəngə boyanmalıdır.
Rəngləmə işini həyata keçirmək üçün baş rəssam ən yeni texnologiyadan istifadə etməyə qərar verdi. Bu işlə xüsusi bir robot məşğul olacaq və robot bir saat ərzində seçilmiş hər hansı bir hasar hissəsini (yandakı lövhələr dəsti) müəyyən bir rəngə boyaya bilər. İşin mümkün qədər tez tamamlanması üçün robotun proqramı elə tərtib edilməlidir ki, tələb olunan rəngləmə minimal vaxtda başa çatsın. Hər hansı bir lövhəni rəngləmədən buraxmaq qəti qadağandır.
Giriş verilənləri
Giriş faylının birinci sətrində n (1 ≤ n ≤ 300) ədədi verilir, burada n - hasardakı lövhələrin sayını göstərir. İkinci sətir isə hasarın tələb olunan rənglənməsini təsvir edən n simvoldan ibarət bir sətirdir. Rənglər böyük latın hərfləri ilə ifadə olunur.
Çıxış verilənləri
Çıxış faylının birinci sətrində hasarın rənglənməsi üçün tələb olunan minimal vaxtı saatlarla ifadə edən m ədədini yazın. Sonrakı m sətir robot üçün rəngləmə proqramını göstərməlidir. Hər bir sətir iki ədəd l_{i} və r_{i}, həmçinin rəngi göstərən böyük latın hərfi c_{i} ehtiva etməlidir. Bu, robotun l_{i}-ci lövhədən r_{i}-ci lövhəyə qədər olan hasar hissəsini c_{i} rənginə boyamalı olduğunu bildirir (hasarın uzunluğu ndirsə, 1 ≤ l_{i} ≤ r_{i} ≤ n olmalıdır).