Ассистентlər
Professor Baytazar böyük bir elmi layihəyə rəhbərlik edir. Layihənin tamamlanması üçün onun n müstəqil təcrübə aparması lazımdır (bu təcrübələr 1-dən n-ə qədər tam ədədlərlə nömrələnmişdir).
Hər bir təcrübəni professor özü apara bilər və ya köməkçiyə həvalə edə bilər. Əgər Baytazar i-ci təcrübəni özü aparmağa qərar verərsə, bu iş ona p_i ardıcıl günə başa gələcək. Bu müddət ərzində o, başqa işlərlə məşğul ola bilməz. Əgər Baytazar təcrübəni köməkçiyə həvalə edərsə, köməkçi seçimi üçün bir gün sərf etməlidir (Baytazar hər şeyi əsaslı şəkildə etməyə alışdığı üçün, həmin gün başqa işlərə diqqətini yayındıra bilməz). Tapılan köməkçi növbəti gün işə başlayır və təcrübəni a_i ardıcıl gün ərzində aparacaq. Bu müddətdə professor başqa işlərlə məşğul ola bilər. Baytazarın layihədə hələ iştirak etməmiş ixtisaslı köməkçi tapa biləcəyi qəbul edilir.
Professor sizdən layihəni mümkün qədər tez başa çatdırmaq üçün fəaliyyət cədvəli tərtib etməyinizi xahiş etdi.
Giriş verilənləri
Girişin ilk sətiri layihənin tamamlanmasına qədər Baytazara qalan təcrübələrin sayı olan n (1 ≤ n ≤ 500000) tam ədədini ehtiva edir.
Sonra n sətir gəlir, i-ci sətir i-ci təcrübə üçün professor və köməkçiyə lazım olan günlərin sayını göstərən iki tam ədəd p_i və a_i (1 ≤ p_i ≤ a_i ≤ 10^9) ehtiva edir.
Çıxış verilənləri
Birinci sətirdə layihənin tamamlanması üçün lazım olan minimum günlərin sayı olan bir tam ədəd k çıxarın. Sonrakı n sətirdə layihəni k gün ərzində başa çatdırmağa imkan verən təcrübələrin cədvəlini çıxarın.
Sonra n sətir gəlməlidir, i-ci sətir i-ci təcrübənin cədvəlini ehtiva etməlidir: əgər professor i-ci təcrübəni özü aparırsa, əvvəlcə "B" hərfi, əgər köməkçiyə həvalə edirsə, "A" hərfi, sonra isə boşluqdan sonra professorun təcrübə üzərində işə başlayacağı günü göstərən t_i (1 ≤ t_i ≤ k) ədədi gəlməlidir (bu halda təcrübə t_i+p_i-1 günündə başa çatacaq) və ya köməkçi axtaracağı günü göstərən ədədi gəlməlidir (köməkçi (t_i+1)-ci gündən (t_i+a_i)-ci günə qədər işləyəcək).
Əgər optimal cədvəllər bir neçədirsə, istənilən birini çıxarın.