Byteasar 给他的儿子 Bytie 买了一套编号从 $1$ 到 $n$ 的积木，并将它们按某种顺序排成一行。Bytie 的目标是将这些积木重新排列，使它们按从小到大的自然顺序排列。然而，Bytie 只允许进行以下两种操作：

• 将最后一块积木移到最前面（操作 a），以及
• 将第三块积木移到最前面（操作 b）。

请编写一个程序，判断给定的积木排列是否可以被正确排序，如果可以，请给出正确的操作序列。

输入格式

输入的第一行包含一个整数 $n$，$1 \le n \le 2\,000$。第二行包含 $n$ 个 $1$ 到 $n$ 之间的整数，由空格分隔。每个数字只出现一次，因此它们代表了积木的初始排列。

输出格式

如果不存在能将积木按数字从小到大排序的操作序列，程序应输出 "NIE DA SIE"（波兰语中意为“不可能”），不含引号。

否则，第一行应输出一个整数 $m$ ($m \leq n^2$)，表示操作的次数。一次操作是指对 a 或 b 进行 $k$ 次连续执行。

如果 $m > 0$，则第二行应输出一个包含 $m$ 个整数的序列，每个整数后紧跟 a 或 b。例如，$k$a（其中 $0 < k < n$）表示连续执行 $k$ 次操作 a。同理，$k$b（其中 $0 < k < n$）表示连续执行 $k$ 次操作 b。

此外，第二行中数字后紧跟的字符必须交替出现。

如果存在多种解，程序可以任意选择其中一种。

样例

样例输入 1

4
1 3 2 4

样例输出 1

4
3a 2b 2a 2b

样例输入 2

7
1 3 2 4 5 6 7

样例输出 2

NIE DA SIE

样例输入 3

3
1 2 3

样例输出 3

0