19589번 - 카드 셔플

문제

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

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

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

입력

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

출력

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

제한

힌트

카드 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

가 된다.