货架整理

故事背景

超市准备进行“货架整列”行动。货架上有一排序号为 1…n 的商品，每件商品的标签上写着一个整数值。运维同学下发了 k 条“整理指令”，每条指令给出一个闭区间 [l, r]，要求把该区间内的商品标签从小到大就地排序。

为保证后下发的指令优先级更高，运维规定：先将所有指令按 (l 降序, r 降序) 的顺序排列，再按照这个顺序依次执行区间内的升序排序。请你输出最终的货架标签序列。

题目描述

给定长度为 n 的整数序列 a_1 … a_n，以及 k 个闭区间 [l_i, r_i]（1 ≤ l_i ≤ r_i ≤ n）。先将这 k 个区间按照“左端点从大到小、若左端点相同则右端点从大到小”的规则排序，然后按此顺序依次对对应子数组 a[l_i … r_i] 进行升序排序。输出所有操作完成后的序列。

输入格式

• 第一行：两个整数 n, k（1 ≤ n ≤ 1000，0 ≤ k ≤ 1000）。
• 第二行：n 个整数 a_i（|a_i| ≤ 10^9）。
• 接下来 k 行：每行两个整数 l_i, r_i（1 ≤ l_i ≤ r_i ≤ n）。

输出格式

• 输出一行，包含 n 个整数，为最终的序列。

输入输出样例 #1

输入 #1

8 3
5 2 4 3 8 1 6 7
2 5
4 7
1 3

输出 #1

2 4 5 1 3 6 8 7

样例解释 #1

指令按 (l 降序, r 降序) 排序：[(4,7), (2,5), (1,3)]。

• 执行 (4,7)：排序 a[4..7] = [3,8,1,6] → [1,3,6,8]，序列变为 [5,2,4,1,3,6,8,7]
• 执行 (2,5)：排序 a[2..5] = [2,4,1,3] → [1,2,3,4]，序列变为 [5,1,2,3,4,6,8,7]
• 执行 (1,3)：排序 a[1..3] = [5,1,2] → [1,2,5]，序列变为 [1,2,5,3,4,6,8,7]