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

Нужно сгенерировать и вывести на экран в лексикографическом порядке все последовательности длины $$$N$$$ из букв A и B.

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

В первой строке задано одно целое число $$$N$$$. $$$(1 \leqslant N \leqslant 9)$$$

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

Выведите все требуемые строки в лексикографическом порядке.

Пример

Входные данные
3
Выходные данные
AAA
AAB
ABA
ABB
BAA
BAB
BBA
BBB