Sequence and Shift Queries

You are given an integer sequence [a1, a2, ..., aN] of length N. Write a program that performs the following operations in order and then prints the sequence.

• 1 i x : add the integer x to ai.
• 2 s : shift the sequence right by s positions.
• 3 s : shift the sequence left by s positions.

Shifting the sequence right by one position turns [a1, a2, …, aN-1, aN] into [aN, a1, a2, …, aN-1].

Shifting the sequence left by one position turns [a1, a2, …, aN-1, aN] into [a2, …, aN-1, aN, a1].

Jinsu wrote code that runs a loop N times for every shift operation, submitted it, and got a time limit exceeded verdict.

The first line gives the length of the sequence N (2 ≤ N ≤ 200,000) and the number of operations Q (1 ≤ Q ≤ 200,000).

The second line gives the integers a1, a2, ..., aN (-10,000 ≤ ai ≤ 10,000).

The next Q lines each contain one operation.

On the first line, print a1, a2, …, aN after performing the Q operations in order, separated by spaces.

• 1 ≤ i ≤ N
• -10,000 ≤ x ≤ 10,000
• 1 ≤ s ≤ N-1