题目描述

译自 POI 2011 Round 1. D「Shift」

Byteasar 给他的儿子 Bytie 买了一盒共 $n$ 块积木，他将这些积木从 $1$ 到 $n$ 编号，并按照一定的顺序摆成一排。Bytie 要将这些积木按照编号从小到大的顺序重新排列，但他只能做下面两种操作：

• 操作 a：将最后一个积木移到最前面。
• 操作 b：把第三个积木移到最前面。

我们将连续进行 $k$ 次同一个操作称为「一块操作」，表示为 $k a$ 或 $k b$。

你需要帮助 Bytie 写一个程序，告诉他有没有一个操作序列能够使积木按照编号从小到大的顺序重新排列，并告诉他操作序列。

输入格式

输入的第一行包含一个整数 $n$，表示积木的个数。
第二行包含 $n$ 个整数，表示积木初始的排列顺序，没有重复的数字。

输出格式

如果没有一种方案能将积木按照编号从小到大的顺序重新排列，你应当输出 NIE DA SIE（波兰语中的 There is no way）。

否则，第一行你应当输出一个整数 $m$，表示操作的块数，$m$ 必须满足 $m \le n^2$。
第二行表示这 $m$ 块操作，每块操作之间用空格隔开。
每一块包含操作数 $k$ 和操作方式，中间没有空格，如 $3a$（$3$ 次 a 操作）。
需要满足相邻两块操作的种类不同，每块操作中进行的次数 $0 \lt k \lt n$。

样例

样例 1

输入
4
1 3 2 4

输出
4
3a 2b 2a 2b

样例 2

输入
7
1 3 2 4 5 6 7

输出
NIE DA SIE

样例 3

输入
3
1 2 3

输出
0

数据范围与提示

对于 $100\%$ 的数据，$1 \le n \le 2000$。

Task authors: Krzysztof Diks & Wojciech Rytter.
翻译和 SPJ: ceba.