{"raw_statement":[{"iden":"statement","content":"Сокровища короны скрыты в сейфе, который находится под наблюдением охраны. Однако охранник время от времени отходит на перерыв, и у грабителя Буратино появляется шанс взломать сейф.\n\nПолистав «Справочник юного взломщика», Буратино узнал, что код к сейфам подобной конструкции обязательно удовлетворяет грамматике, определяемой следующей формой Бэкуса-Наура:\n\nДругими словами, если c — произвольный корректный код, то AcX и BcY — также корректный код; кроме того, если c1 и c2 — произвольные корректные коды, то c1c2 — также корректный код.\n\nТакже Буратино выяснил, что код данного конкретного сейфа должен состоять ровно из N символов. В момент, когда в сейф положили сокровища и закрыли его дверцу, значение кода было следующим:\n\nЗатем каждую секунду код изменялся на лексикографически минимальный корректный код, больший текущего, а в том случае, если текущий код являлся максимально возможным, — на показанный выше стартовый код.\n\nБуратино тщательно замерил время, прошедшее с момента закрытия дверцы сейфа. Помогите ему подобрать код к сейфу.\n\nВвод содержит целое чётное число N и целое число T (2 ≤ N ≤ 30, 0 ≤ T ≤ 1018) — соответственно длину кода и количество секунд, прошедших с момента закрытия сейфа.\n\nВыведите строку, состоящую из N символов 'A', 'X', 'B', 'Y', — код к сейфу в момент времени T.\n\n"},{"iden":"входные данные","content":"Ввод содержит целое чётное число N и целое число T (2 ≤ N ≤ 30, 0 ≤ T ≤ 1018) — соответственно длину кода и количество секунд, прошедших с момента закрытия сейфа."},{"iden":"выходные данные","content":"Выведите строку, состоящую из N символов 'A', 'X', 'B', 'Y', — код к сейфу в момент времени T."},{"iden":"примеры","content":"Входные данные6 0Выходные данныеAAAXXXВходные данные6 1Выходные данныеAABYXXВходные данные6 2Выходные данныеAAXAXXВходные данные6 3Выходные данныеAAXBYXВходные данные6 4Выходные данныеAAXXAXВходные данные6 10Выходные данныеABYXAX"}],"translated_statement":null,"sample_group":[],"show_order":[],"formal_statement":"**Definitions**  \nLet $\\Sigma = \\{A, X, B, Y\\}$.  \nLet $L \\subseteq \\Sigma^*$ be the language generated by the grammar:  \n- Base: $\\varepsilon \\in L$  \n- Rules: If $c \\in L$, then $AcX \\in L$ and $BcY \\in L$  \n- Concatenation: If $c_1, c_2 \\in L$, then $c_1c_2 \\in L$  \n\nLet $L_N = \\{ w \\in L \\mid |w| = N \\}$ be the set of valid codes of length $N$.  \n\n**Constraints**  \n1. $N \\in 2\\mathbb{Z}$, $2 \\leq N \\leq 30$  \n2. $T \\in \\mathbb{Z}$, $0 \\leq T \\leq 10^{18}$  \n3. The initial code at $T=0$ is the lexicographically smallest element of $L_N$.  \n\n**Objective**  \nGiven $N$ and $T$, find the $T$-th code in the cyclic lexicographically ordered sequence of $L_N$, where:  \n- The sequence starts at the lex-minimal code in $L_N$  \n- Each subsequent code is the lexicographically next valid code in $L_N$  \n- After the lex-maximal code, the sequence wraps to the lex-minimal code  \n\nOutput the code at time $T$:  \n$$\n\\text{code}(T) = \\text{the } (T \\bmod |L_N|)\\text{-th element in the lex-ordered list of } L_N\n$$","simple_statement":"Given a string of length N made of characters 'A', 'X', 'B', 'Y', starting from \"AX\", and each second it changes to the next valid code in lex order (wrapping back to \"AX\" after the last), find the code after T seconds.","has_page_source":false}