정렬하기

길이 $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$