У вас есть последовательность \(a_1, a_2, \ldots, a_n\) длины \(n\), состоящая из целых чисел от \(1\) до \(m\). Также у вас есть строка \(s\), состоящая из \(m\) латинских букв «B».
Вы примените \(n\) операций к этой строке.
- На \(i\)-й (\(1 \le i \le n\)) операции вы можете заменить \(a_i\)-й либо \((m + 1 - a_i)\)-й символ строки \(s\) на «A». Можно заменять символ на одной и той же позиции несколько раз.
Найдите лексикографически минимальную строку, которую Вы можете получить после выполнения всех операций.
Строка \(x\) лексикографически меньше строки \(y\) такой же длины, если и только если в первой позиции, где \(x\) и \(y\) различны, в строке \(x\) находится буква, которая встречается в алфавите раньше, чем соответствующая буква в \(y\).
Выходные данные
Для каждого набора входных данных выведите строку длины \(m\) — лексикографически минимальную строку, которую можно получить. Каждый символ строки должен быть заглавной латинской буквой «A» или заглавной латинской буквой «B».
Примечание
В первом наборе входных данных последовательность \(a = [1, 1, 3, 1]\). Одно из возможных решений следующее.
- На \(1\)-й операции вы можете заменить \(1\)-й символ строки \(s\) на A. После этого \(s\) становится равной ABBBB.
- На \(2\)-й операции вы можете заменить \(5\)-й символ строки \(s\) на A (так как \(m+1-a_2=5\)). После этого \(s\) становится равной ABBBA.
- На \(3\)-й операции вы можете заменить \(3\)-й символ строки \(s\) на A. После этого \(s\) становится равной ABABA.
- На \(4\)-й операции вы можете заменить \(1\)-й символ строки \(s\) на A. После этого \(s\) остаётся равной ABABA.
Вы получите строку
ABABA. Можно показать, что нельзя получить лексикографически меньшую строку.
Во втором наборе входных данных вы сделаете только одну операцию. Вы можете заменить \(2\)-й либо \(4\)-й символ строки \(s\) на A. Вы можете получить строки BABBB и BBBAB после операции. Строка BABBB является лексикографически наименьшей из этих строк.
В третьем наборе входных данных вы можете получить только строку A.
В четвёртом наборе входных данных вы можете заменить \(1\)-й и \(2\)-й символы строки \(s\) на A, чтобы получить строку AABB.
В пятом наборе входных данных вы можете заменить \(1\)-й и \(3\)-й символы строки \(s\) на A, чтобы получить строку ABABBBB.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
6
4 5
1 1 3 1
1 5
2
4 1
1 1 1 1
2 4
1 3
2 7
7 5
4 5
5 5 3 5
|
ABABA
BABBB
A
AABB
ABABBBB
ABABA
|