수열과 쿼리 6

문제

길이가 $N$인 수열 $A_1, A_2, \dots, A_N$이 주어진다. 이때, 다음 쿼리를 수행하는 프로그램을 작성해 보자.

• l r: $l \le i \le r$을 만족하는 모든 $i$에 대하여, $A_i$를 정렬 대상으로 지정한다. ($1 \le l \le r \le N$)

모든 쿼리가 주어지면, 하나 이상의 쿼리에 의해 정렬 대상으로 지정된 모든 위치의 집합을 구한다. 이 위치들의 집합은 여러 개의 연속된 구간으로 나누어질 수 있다. 이렇게 구해진 각 연속된 구간에 속한 원소들을 각각 오름차순으로 정렬해야 한다.

최종적으로 수열의 각 원소가 어떤 값을 가지고 있는지 출력하는 프로그램을 작성하시오.

입력

첫째 줄에 수열의 크기 $N$과 쿼리의 개수 $Q$가 공백으로 구분되어 주어진다. ($1 \le N, Q \le 100,000$)

둘째 줄에 수열 $A$를 구성하는 $N$개의 정수 $A_1, A_2, \dots, A_N$이 공백으로 구분되어 주어진다. ($-10^9 \le A_i \le 10^9$)

셋째 줄부터 $Q$개의 줄에 걸쳐 각 쿼리를 나타내는 두 정수 $l, r$이 공백으로 구분되어 주어진다. ($1 \le l \le r \le N$)

출력

모든 정렬 작업이 완료된 후의 최종 수열 $A_1, A_2, \dots, A_N$을 한 줄에 공백으로 구분하여 출력한다.

예제 입력 1

5 2
5 4 3 2 1
1 3
4 5

예제 출력

1 2 3 4 5

예제 입력 2

5 2
5 4 3 2 1
1 3
5 5

예제 출력 2

1 3 4 2 5