Сокровища короны скрыты в сейфе, который находится под наблюдением охраны. Однако охранник время от времени отходит на перерыв, и у грабителя Буратино появляется шанс взломать сейф.
Полистав «Справочник юного взломщика», Буратино узнал, что код к сейфам подобной конструкции обязательно удовлетворяет грамматике, определяемой следующей формой Бэкуса-Наура:
Другими словами, если c — произвольный корректный код, то AcX и BcY — также корректный код; кроме того, если c1 и c2 — произвольные корректные коды, то c1c2 — также корректный код.
Также Буратино выяснил, что код данного конкретного сейфа должен состоять ровно из N символов. В момент, когда в сейф положили сокровища и закрыли его дверцу, значение кода было следующим:
Затем каждую секунду код изменялся на лексикографически минимальный корректный код, больший текущего, а в том случае, если текущий код являлся максимально возможным, — на показанный выше стартовый код.
Буратино тщательно замерил время, прошедшее с момента закрытия дверцы сейфа. Помогите ему подобрать код к сейфу.
Ввод содержит целое чётное число N и целое число T (2 ≤ N ≤ 30, 0 ≤ T ≤ 1018) — соответственно длину кода и количество секунд, прошедших с момента закрытия сейфа.
Выведите строку, состоящую из N символов 'A', 'X', 'B', 'Y', — код к сейфу в момент времени T.
## Входные Данные
Ввод содержит целое чётное число N и целое число T (2 ≤ N ≤ 30, 0 ≤ T ≤ 1018) — соответственно длину кода и количество секунд, прошедших с момента закрытия сейфа.
## Выходные Данные
Выведите строку, состоящую из N символов 'A', 'X', 'B', 'Y', — код к сейфу в момент времени T.
## Примеры
Входные данные6 0Выходные данныеAAAXXXВходные данные6 1Выходные данныеAABYXXВходные данные6 2Выходные данныеAAXAXXВходные данные6 3Выходные данныеAAXBYXВходные данные6 4Выходные данныеAAXXAXВходные данные6 10Выходные данныеABYXAX
[samples]
**Definitions**
Let $\Sigma = \{A, X, B, Y\}$.
Let $L \subseteq \Sigma^*$ be the language generated by the grammar:
- Base: $\varepsilon \in L$
- Rules: If $c \in L$, then $AcX \in L$ and $BcY \in L$
- Concatenation: If $c_1, c_2 \in L$, then $c_1c_2 \in L$
Let $L_N = \{ w \in L \mid |w| = N \}$ be the set of valid codes of length $N$.
**Constraints**
1. $N \in 2\mathbb{Z}$, $2 \leq N \leq 30$
2. $T \in \mathbb{Z}$, $0 \leq T \leq 10^{18}$
3. The initial code at $T=0$ is the lexicographically smallest element of $L_N$.
**Objective**
Given $N$ and $T$, find the $T$-th code in the cyclic lexicographically ordered sequence of $L_N$, where:
- The sequence starts at the lex-minimal code in $L_N$
- Each subsequent code is the lexicographically next valid code in $L_N$
- After the lex-maximal code, the sequence wraps to the lex-minimal code
Output the code at time $T$:
$$
\text{code}(T) = \text{the } (T \bmod |L_N|)\text{-th element in the lex-ordered list of } L_N
$$