13159번 - 배열

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

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

[a₁,…a_l-1,a_r,a_r-1,…,a_l+1,a_l,a_r+1,…,a_N]

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

[a₁,…a_l-1,a_r-x+1,…,a_r-1,a_r,a_l,a_l+1,…,a_r-x,a_r+1,…,a_N]

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

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

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

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

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