Асистенти
Професор Байтазар керує великим науковим проєктом. Для завершення проєкту йому потрібно провести n незалежних експериментів (пронумерованих від 1 до n).
Кожен експеримент професор може виконати сам або доручити асистенту. Якщо Байтазар вирішує виконати i-й експеримент самостійно, він повинен витратити p_i підряд днів, протягом яких не може займатися іншими справами. Якщо ж експеримент доручено асистенту, Байтазар витрачає один день на його пошук (оскільки він завжди підходить до справи ґрунтовно, то в цей день не може займатися іншими справами). Знайдений асистент починає роботу наступного дня і виконує експеримент протягом a_i підряд днів, в той час як професор може займатися іншими справами. Вважається, що Байтазар завжди може знайти кваліфікованого асистента, який ще не задіяний у проєкті.
Професор попросив вас скласти розклад його дій так, щоб завершити проєкт якомога швидше.
Вхідні дані
Перший рядок вводу містить ціле число n (1 ≤ n ≤ 500000) - кількість експериментів, які залишилося провести Байтазару.
Далі йде n рядків, де i-й рядок містить два цілі числа p_i і a_i (1 ≤ p_i ≤ a_i ≤ 10^9), що вказують на кількість днів, необхідних для виконання i-го експерименту професором і асистентом відповідно.
Вихідні дані
У першому рядку виведіть одне ціле число k - мінімальну кількість днів, необхідну для завершення проєкту. У наступних n рядках виведіть розклад експериментів, що дозволяє завершити проєкт за k днів.
Кожен з наступних n рядків повинен містити графік i-го експерименту: спочатку літера "B" якщо професор проводить i-й експеримент самостійно, або "A" якщо він доручає експеримент асистенту, а потім через пробіл число t_i (1 ≤ t_i ≤ k) - день, коли професор почне роботу над експериментом (експеримент завершиться в день t_i+p_i-1), або коли він буде шукати асистента (який буде працювати з (t_i+1)-го дня по (t_i+a_i)-й).
Якщо існує декілька оптимальних розкладів, виведіть будь-який з них.