Закордонна подорож
Обмеження: 2 сек., 256 МіБ
Усе більше країн знову відкривають свої кордони після пандемії реп’яховірусу. Марічка та Зеник вирішили поїхати зі своїми друзями в подорож. Для цього їм усім потрібно вакцинуватися.
Друзі пішли до поліклініки, відстояли в гігантській черзі та придбали великий ящик з вакцинами — x доз першого типу та y доз другого типу. Тепер кожному з n учасників поїздки треба визначитися, яким типом вакцини він буде щеплюватися. Відомо, що користь від вакцинації i-го учасника групи вакциною першого типу дорівнює ai, а вакциною другого типу — bi.
Друзі хочуть розподілити вакцини між учасниками так, щоб кожен учасник отримав рівно по одній дозі вакцини та сумарна користь була максимальною. Допоможете їм?
Вхідні дані
У першому рядку задано три цілі числа n, x та y — кількість учасників поїздки, кількість доз першого типу та кількість доз другого типу.
У кожному з наступних n рядків задано по два цілих числа ai та bi — користь від вакцинації відповідного учасника кожним з типів вакцини.
Вихідні дані
Виведіть один рядок з n
символів. i-й символ рівний
A
, якщо i-тому
учаснику слід прийняти вакцину першого типу, B
— другу.
Якщо способів досягнути максимальної користі кілька, то виведіть
довільний з них.
Обмеження
1≤n≤105,
0≤x,y≤2⋅105,
x+y≥n,
0≤ai,bi≤109.
Приклади
Вхідні дані (stdin) | Вихідні дані (stdout) |
---|---|
4 2 2 1 3 7 4 9 2 3 3 | BAAB |
Примітки
Сумарна користь складе 22. Більшого значення досягнути не можна.