시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
10 초 (추가 시간 없음) 1024 MB 60 25 19 55.882%

문제

위에서부터 1, 2, ..., N이 적혀 있는 카드 한 벌이 있다. 이 때, 1 ≤ xyN인 두 정수 x, y에 대해 다음 쿼리를 수행한다.

  • 1 x y : 위에서부터 x번째에 있는 카드부터 y번째에 있는 카드까지를 제일 위로 올린다.
  • 2 x y : 위에서부터 x번째에 있는 카드부터 y번째에 있는 카드까지를 제일 아래로 내린다.
  • 3 x y : 위에서부터 x번째에 있는 카드부터 y번째에 있는 카드까지 리플 셔플을 한다. yx + 1은 1,000 이하이다.

리플 셔플N장의 카드가 있을 때 카드를 위에서부터 ⌊(N + 1) / 2⌋장의 카드 덩어리와 나머지 덩어리로 나눈 후 교대로 카드를 두는 방식으로 카드를 섞는 것이다. 섞기 전에 제일 위에 있었던 카드가 섞은 후에도 제일 위로 오도록 한다.

입력

첫 줄에 카드 수 N(1 ≤ N ≤ 106)과 쿼리의 수 Q(1 ≤ ≤ 2 × 105)가 주어진다. 다음 Q개의 줄에 쿼리가 주어진다.

출력

카드를 다 섞고 난 뒤 카드에 어떤 숫자가 적혀 있는지 위에서부터 순서대로 출력한다.

예제 입력 1

6 3
1 2 3
2 4 5
3 1 6

예제 출력 1

2 6 3 4 1 5

힌트

카드 6장이 있을 때 쿼리 3 1 6을 처리하면

1 2 3 4 5 6 ⇒ 1 4 2 5 3 6

이 되고, 카드 7장이 있을 때 3 1 7이 입력으로 들어오면 

1 2 3 4 5 6 7 ⇒ 1 5 2 6 3 7 4

가 된다.