시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 1024 MB0000.000%

문제

Consider a roll of N paper towels. The roll is unrolled on the floor and its towels are numbered from 1 to N, from left to right. We then perform several folding operations. Specifically, a fold at position p consists of lifting all the towels to the right of the p-th towel and flipping them leftwards. For example, if N = 7, then a fold at position 2 looks like:

Before After
1 2 3 4 5 6 7
_ _ _ 4 3
7 6 5 1 2

Note that fold positions refer to the towels touching the floor, not necessarily to the numbers on them. For example, if we now perform a fold at position 2 , the result is:

Before After
_ _ _ 4 3
7 6 5 1 2
_ 1 _
2 4 5
3 7 6

Folding can also occur at position 0 . In that case we flip over the entire roll.

You are given the initial length of the towel, N, and M folding operations to perform. You must print various details about the final configuration of the paper towels.

입력

The first line contains two integers N and M, representing the length of the roll and the number of operations to perform. Each of the following M lines contains one integer, the position of the fold.

출력

  • The first line should contain the numbers on the towels making up the tallest stack, from bottom to top. If multiple stacks exist with the same maximum height, print the contents of the leftmost stack.
  • The second line should contain the numbers on the towels touching the floor, from left to right.
  • The third line should contain the numbers on the towels visible from above, from left to right.

제한

  • 1 ≤ N ≤ 106
  • 1 ≤ M ≤ 106
  • 0 ≤ p < L for every fold operation at position p, where L is the remaining length of the roll at the me of the fold.

서브태스크

번호배점제한
120

N, M ≤ 103

240

N, M ≤ 105

340

none

예제 입력 1

8 3
6
1
2

예제 출력 1

7 6 3
2 7 8
1 3 4

힌트

The initial layout is

1 2 3 4 5 6 7 8

After the first operation the layout is

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

After the second operation the layout is

6 5 _ _ 2
7 8 4 3 1

After the third operation the layout is

_ 3 4
1 6 5
2 7 8

채점 및 기타 정보

  • 예제는 채점하지 않는다.