Сокровища короны скрыты в сейфе, который находится под наблюдением охраны. Однако охранник время от времени отходит на перерыв, и у грабителя Буратино появляется шанс взломать сейф.

Полистав «Справочник юного взломщика», Буратино узнал, что код к сейфам подобной конструкции обязательно удовлетворяет грамматике, определяемой следующей формой Бэкуса-Наура:

Другими словами, если c — произвольный корректный код, то AcX и BcY — также корректный код; кроме того, если c₁ и c₂ — произвольные корректные коды, то c_1c2 — также корректный код.

Также Буратино выяснил, что код данного конкретного сейфа должен состоять ровно из N символов. В момент, когда в сейф положили сокровища и закрыли его дверцу, значение кода было следующим:

Затем каждую секунду код изменялся на лексикографически минимальный корректный код, больший текущего, а в том случае, если текущий код являлся максимально возможным, — на показанный выше стартовый код.

Буратино тщательно замерил время, прошедшее с момента закрытия дверцы сейфа. Помогите ему подобрать код к сейфу.