题目描述

有一卷由 $N$ 张纸巾组成的长条。最初整卷纸巾被展开在地面上，从左到右编号为 $1,2,\ldots,N$。

接下来要执行若干次折叠操作。当前长条与地面接触的纸巾列数记为 $L$。一次在位置 $p$ 的折叠定义如下：

• 若 $p>0$，则从当前从左往右数第 $p$ 张接触地面的纸巾的右侧开始，把右边所有部分整体拿起，并向左翻折；
• 若 $p=0$，则把整卷纸巾整体翻转。

注意，折叠位置是按照当前接触地面的纸巾列来计算的，而不一定是按照纸巾原来的编号来计算。

例如，若 $N=7$，初始状态为：

1 2 3 4 5 6 7

在位置 $2$ 折叠后，结果可以表示为：

_ _ _ 4 3
7 6 5 1 2

其中下方一行表示接触地面的纸巾，上方表示叠在其上的纸巾。

再在当前位置 $2$ 折叠，折叠位置仍然是按照接触地面的纸巾列来数，结果为：

_ 1 _
2 4 5
3 7 6

现在给定初始长度 $N$ 和 $M$ 次折叠操作，请输出最终纸巾堆叠状态的若干信息。

输入格式

第一行包含两个整数 $N,M$，分别表示纸巾卷的初始长度和折叠操作次数。

接下来 $M$ 行，每行包含一个整数 $p$，表示一次折叠的位置。

输出格式

输出三行。

第一行输出最高纸巾堆中所有纸巾的编号，按照从下到上的顺序输出。如果有多个最高纸巾堆，输出最左边的那个。

第二行输出所有接触地面的纸巾编号，按照从左到右的顺序输出。

第三行输出所有从上方可见的纸巾编号，按照从左到右的顺序输出。

数据范围与约定

• $1\le N\le 10^6$；
• $1\le M\le 10^6$；
• 对于每次折叠，$0\le p<L$，其中 $L$ 是该次折叠前当前纸巾卷与地面接触的列数。

子任务

样例

输入

8 3
6
1
2

输出

7 6 3
2 7 8
1 3 4

样例解释

初始状态为：

1 2 3 4 5 6 7 8

第一次折叠后：

_ _ _ _ 8 7
1 2 3 4 5 6

第二次折叠后：

6 5 _ _ 2
7 8 4 3 1

第三次折叠后：

_ 3 4
1 6 5
2 7 8

所以最高堆为从下到上 $7,6,3$，接触地面的纸巾从左到右为 $2,7,8$，从上方可见的纸巾从左到右为 $1,3,4$。