Card Shuffle

Time limit10sMemory limit1024 MB

Summary

Given a deck of N cards, apply Q queries that move a range to the top or bottom or ripple-shuffle it, then print the final order.

Level: Medium6 of 10
Topics: Tree, Simulation
Solved: No attempts yet

Problem

A deck of cards numbered $1, 2, \ldots, N$ from top to bottom is given. For two integers $x$ and $y$ with $1 \le x \le y \le N$ , perform the following queries.

1 x y: Move the cards from the $x$ -th to the $y$ -th position (counted from the top) to the top of the deck.
2 x y: Move the cards from the $x$ -th to the $y$ -th position (counted from the top) to the bottom of the deck.
3 x y: Perform a ripple shuffle on the cards from the $x$ -th to the $y$ -th position (counted from the top). $y - x + 1$ is at most 1,000.

A ripple shuffle splits the $N$ cards into a top pile of $\lfloor (N + 1) / 2 \rfloor$ cards and the remaining pile, then places cards alternately from the two piles. The card that was on top before the shuffle stays on top after the shuffle.

Input

The first line contains the number of cards $N$ ( $1 \le N \le 10^6$ ) and the number of queries $Q$ ( $1 \le Q \le 2 \times 10^5$ ). The next $Q$ lines each contain one query.

Output

After all queries are processed, print the numbers on the cards in order from top to bottom.

Hint

With 6 cards, processing the query 3 1 6 gives

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

With 7 cards, the input 3 1 7 gives

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

Examples1

Example 1
Input
```
6 3
1 2 3
2 4 5
3 1 6
```
Expected output
```
2 6 3 4 1 5
```