정렬하기

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