题目描述

今天名飞送给了灰灰一个神奇的玩具。
这个玩具由两个量筒和一行排列好的共\(N\)个数字块组成。

名飞事后跟我说量筒是他从化学实验室偷出来的，还偷了浓硫酸，以后的题目会出现。

灰灰可以把数字块放入量筒，但是当量筒中有多个数字块的时候，灰灰只能先拿出最上面的数字块，再依次拿下面的。（Stack后进先出）
名飞交给了灰灰一个小任务，让他在遵守量筒的后进后出的规则下，对这行数字块进行排序，使得最后所有数字块从量筒中拿出来后组成的序列单调递增。

具体来说共四个操作：

• 操作a：将最前面的数字块放入量筒1。
• 操作b：将量筒1的最顶端数字块拿出，放到数字块序列尾部。
• 操作c：将最前面的数字块放入量筒2。
• 操作d：将量筒2的最顶端数字块拿出，放到数字块序列尾部。

输入格式

第一行是一个整数\(n\)。
第二行有\(n\)个用空格隔开的正整数，构成一个\(1\)∼\(n\)的排列。

输出格式

共一行，如果输入的排列无法排序，输出0。
否则输出字典序最小的操作序列，每两个操作之间用空格隔开，行尾没有空格。

样例

输入

4
1 3 2 4

输出

a b a a b b a b

数据规模

\(n \leqslant 1000\)

来源

洛谷P1155