29082번 - 정렬하기

문제

길이 $N$의 수열 $A$가 주어진다. $A$에는 1ドル$부터 $N$까지의 정수가 한 번씩 등장한다. 이 수열에서 다음과 같은 쿼리들을 $Q$번 수행해보자.

• 1ドル$ $l$ $r$: $A_l,\cdots ,A_r$을 오름차순 정렬한다.
• 2ドル$ $l$ $r$: $A_l,\cdots ,A_r$을 내림차순 정렬한다.
• 3ドル$ $l$ $r$: $A_l+\cdots +A_r$을 구한다.

또한, 모든 쿼리를 수행한 후 $A$의 최종 상태를 출력해야 한다.

입력

첫 번째 줄에 $N$과 $Q$가 공백으로 구분되어 주어진다.

두 번째 줄에 $N$개의 수 $A_1,\cdots ,A_N$이 공백으로 구분되어 주어진다.

이후 $Q$개의 줄에 걸쳐 쿼리들의 정보 $k,l,r$이 공백으로 구분되어 주어진다. $k=1$이면 첫 번째 쿼리, $k=2$이면 두 번째 쿼리, $k=3$이면 세 번째 쿼리라는 뜻이다.

출력

세 번째 쿼리가 주어질 때마다 $A_l+\cdots +A_r$을 구해 줄바꿈으로 구분하여 출력한다.

다음 줄에 $N$개의 수를 공백으로 구분하여 출력한다. $i$번째 수는 모든 쿼리를 수행한 후 $A_i$의 값을 출력한다.

제한

• 2ドル\le N\le 100,円 000$
• 1ドル\le Q\le 100,円 000$
• 1ドル\le k\le 3$
• 1ドル\le l\le r\le N$

힌트