Contest.uni-smr.ac.ru :: соревнования по программированию
Русская версия || English version
Login:
Password:
Забыли пароль?
 пример поиска: Вася Пупкин
 

Задача E. Конференция

Задачу добавил: alef

Успешно сдано решений: 103

Ограничение по времени на тест: 2 секунды
Ограничение по памяти на тест: 256 мегабайт

В один из дней почти все сотрудники компании, где проходит стажировку Кеша, отправились на конференцию. Кеше показались наиболее интересными программы двух секций. Сделать между ними выбор Кеша так и не смог, поэтому решил, что попробует послушать доклады и там, и там.

В каждой секции запланировано по n докладов, причём регламент секций совершенно одинаков. Это значит, что доклад #i первой секции и доклад #i второй секции начнутся и закончатся одновременно (с учётом вопросов, обсуждений и т.п.).

Кеша определил интересность f1, f2, ..., fn для докладов первой секции и s1, s2, ..., sn для докладов второй секции. К огорчению Кеши, аудитории, где проводятся секции, расположены далеко друг от друга. Поэтому, чтобы перейти из одной аудитории в другую, ему придётся пропустить доклад.

Кеша хочет составить для себя расписание таким образом, чтобы суммарная интересность прослушанных им докладов была максимальной. Ваша задача — определить, какие доклады каких секций Кеша будет слушать.

Входные данные

В первой строке содержится целое число n (1 ≤ n ≤ 2·105) — количество докладов каждой секции.

Во второй строке содержится n целых чисел f1, f2, ..., fn (1 ≤ fi ≤ 105), fi — интересность доклада #i первой секции.

В третьей строке содержится n целых чисел s1, s2, ..., sn (1 ≤ si ≤ 105), si — интересность доклада #i второй секции.

Выходные данные

В первой строке выведите максимально возможную суммарную интересность прослушанных Кешей докладов.

Во второй строке выведите число m — количество докладов, которые прослушает Кеша.

В третьей строке выведите m символов A и B, где символ A означает, что Кеша слушал доклад на первой секции, а символ B — что Кеша слушал доклад на второй секции.

Если существует несколько решений, выведите любое.

Система оценки

Подзадача 1 (до 30 баллов)

1 ≤ n ≤ 1000.

Баллы начисляются в случае прохождения всех тестов подзадачи.

Подзадача 2 (до 70 баллов)

1 ≤ n ≤ 200000.

Баллы начисляются в случае прохождения всех тестов подзадачи.

По запросу сообщается результат проверки на каждом тесте.

Пример

Входные данные
5
3 4 16 2 5
8 6 4 6 7
Выходные данные
31
3
BAB
Примечание

Приведённый в примере ответ не является единственно верным. Также правильными ответами будут, например, строки BAAA и BBBBB (конечно, при этом во второй строке следует выводить 4 и 5 соответственно).

Сдать задачу

Задать вопрос жюри по этой задаче