17499번 - 수열과 시프트 쿼리

문제

백준 온라인 저지를 여행하다 보면 하나의 수열이 주어지고 여기에 여러 가지 연산을 하는 문제들을 만나볼 수 있습니다.

진수는 백준 온라인 저지에서 문제를 풀다 다음과 같은 문제를 찾았습니다.

길이가 N인 정수 수열 [a₁, a₂, ..., a_N] 이 주어진다. 다음과 같은 연산들을 수행한 후 수열을 출력하는 프로그램을 작성하시오.

• 1 i x : a_i에 정수 x만큼 더한다.
• 2 s : 수열을 오른쪽으로 s칸 시프트한다.
• 3 s : 수열을 왼쪽으로 s칸 시프트한다.

수열을 오른쪽으로 한 칸 시프트하면 수열 [a₁, a₂, …, a_N-1, a_N] 은 [a_N, a₁, a₂, …, a_N-1] 이 되고

수열을 왼쪽으로 한 칸 시프트하면 수열 [a₁, a₂, …, a_N-1, a_N] 은 [a₂, …, a_N-1, a_N, a₁] 이 된다.

진수는 빠르게 코딩하여 제출하였는데 '시간 초과' 판정을 받았습니다.

진수가 작성한 코드는 시프트 연산을 수행할 때마다 반복문이 N번 실행되어 너무 느리기 때문입니다.

진수는 이 문제를 풀어 '맞았습니다!!' 를 띄워줄 누군가를 기다리고 있습니다.

입력

첫 번째 줄에 수열의 길이 N (2 ≤ N ≤ 200,000) 과 연산의 개수 Q (1 ≤ Q ≤ 200,000) 가 주어집니다.

두 번째 줄에는 정수 a₁, a₂, ..., a_N (-10,000 ≤ a_i ≤ 10,000) 이 주어집니다.

다음 Q개의 줄에는 각 줄 마다 연산이 주어집니다.

출력

첫 번째 줄에 Q개의 연산을 차례대로 수행한 후 a₁, a₂, …, a_N 을 공백을 사이에 두고 출력합니다.

제한

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

힌트