Given n cards, initial the ith card from left to right has a number i written on it. X shuffled it Q times: The ith shuffle

is given as (l, c, k) meaning: X takes cards from position (not number) l to l + c — 1 out of the deck. Then insert it before

position k. After Q shuffle, print the order (number) written on each card from left to right.

N, Q <= 1e5

Ex:

5 2

3 2 2

3 3 1

Initially: (1, 2, 3, 4, 5)

After 1st queries: (1, 3, 4, 2, 5)

After 2nd queries:(4, 2, 5, 1, 3)

Can someone help? Thanks in advance!

Treap.

Sqrt decomposition on queries with linked lists. (no overkill)