시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 512 MB 67 23 9 23.684%

문제

UCPC 2015년도 우승자 범수, 상수 형제는 가끔 배열을 가지고 논다. 이들은 크기 N인 배열 A=[a1,…,aN]을 가지고 있다. 처음에는 모든 i(1≤i≤N)에 대해 ai=i이다. 이 형제들은 Q개의 질의를 받아 순서대로 해결하면서 논다. 질의는 다음과 같은 네 종류 중 하나이다.

  1.  “1 l r” (1 ≤ l ≤ r ≤ N): al에서 ar사이의 수들에 대해 이들의 최솟값, 최댓값, 합을 구한다. 그리고 al에서 ar사이의 수들을 뒤집는다. 배열을 뒤집고 나면 원래의 배열은 아래와 같이 변할 것이다.

[a1,…al-1,ar,ar-1,…,al+1,al,ar+1,…,aN]

  1.  “2 l r x” (1 ≤ l ≤ r ≤ N, -N < x < N): al에서 ar사이의 수들에 대해 이들의 최솟값, 최댓값, 합을 구한다. 그리고 al에서 ar사이의 수들을 오른쪽으로 x칸만큼 shift한다. 만약 x가 음수라면, 왼쪽으로 -x칸만큼 shift한다. 0 < x ≤ r-l인 경우 원래의 배열은 아래와 같이 변할 것이다.

[a1,…al-1,ar-x+1,…,ar-1,ar,al,al+1,…,ar-x,ar+1,…,aN]

  1.  “3 i” (1 ≤ i ≤ N): ai가 어떤 수인지 구한다.
  2.  “4 x” (1 ≤ x ≤ N): ai=x인 i(1 ≤ i ≤ N)가 어떤 수인지 구한다.

하나의 질의를 수행한 다음 배열이 바뀌고 나면, 그 결과는 다음의 질의에도 영향을 미친다. 이때, 범수, 상수 형제가 질의를 해결할 때마다 구한 값을 출력하고, 모든 질의를 해결한 뒤 마지막 배열의 모습을 출력하라.

입력

입력의 첫 줄에는 배열의 크기를 나타내는 자연수 N과 질의의 수를 나타내는 자연수 Q가 주어진다.(1 ≤ N, Q ≤ 300,000) 그 다음 Q개의 줄에 걸쳐 각 질의의 정보가 네 종류 중 하나의 형식으로 주어진다.

출력

Q개의 줄에 걸쳐 각 질의마다 구해야 하는 값을 공백으로 구분하여 한 줄씩 출력한다. 1번과 2번 질의는 최솟값, 최댓값, 합 순서로 출력하고, 3번과 4번 질의는 구하는 값 하나를 출력한다. 마지막 (Q+1)번째 줄에는 모든 질의를 해결한 후 배열의 값을 공백으로 구분하여 한 줄에 출력한다.

예제 입력

5 5
1 2 4
3 4
2 3 5 1
2 1 3 -2
4 3

예제 출력

2 4 9
2
2 5 10
1 5 10
4
5 1 4 3 2

힌트

[1, 2, 3, 4, 5]→[1, 4, 3, 2, 5]→[1, 4, 5, 3, 2]→[5, 1, 4, 3, 2]