7002: 盒子里的糖果
[Creator : ]
Description
在桌子上摆着 $n$ 个盒子，左数第 $i$ 个盒子里初始装着 $a_i$ 颗糖果。
接下来小 P 进行了 $m$ 次操作，每次操作有参数 $l,r$，小 P 可以选择一个操作执行：
接下来小 P 进行了 $m$ 次操作，每次操作有参数 $l,r$，小 P 可以选择一个操作执行：
- 在左数第 $l$ 个盒子到第 $r$ 个盒子各放入一颗糖果。
- 将左数第 $l$ 个盒子到第 $r$ 个盒子任意重排列。
Input
第一行两个整数 $n,m$ 表示盒子数和操作数。
第二行包含 $n$ 个整数，第 $i$ 个整数 $a_i$ 表示第 $i$ 个盒子初始糖果数。
接下来 $m$ 行每行两个整数 $l,r$ 描述一次操作。
第二行包含 $n$ 个整数，第 $i$ 个整数 $a_i$ 表示第 $i$ 个盒子初始糖果数。
接下来 $m$ 行每行两个整数 $l,r$ 描述一次操作。
Output
输出一行 $n$ 个整数，第 $i$ 个整数表示左数第 $i$ 个盒子中最多有多少糖果。
Constraints
对于 30% 的数据，保证 $n≤5,m≤3$。
对于 60% 的数据，保证 $n,m≤5000$。
对于 100% 的数据，保证 $1≤n,m≤5×10^5,1≤a_i≤10^9,1≤l≤r≤n$。
对于 60% 的数据，保证 $n,m≤5000$。
对于 100% 的数据，保证 $1≤n,m≤5×10^5,1≤a_i≤10^9,1≤l≤r≤n$。
Sample 1 Input
4 5
1 2 2 3
2 2
2 2
1 3
1 3
3 4
Sample 1 Output
5 6 6 5
解释一种让第 $4$ 个盒子糖果数为 $5$ 的方法：
(1,2,2,3)→(1,3,2,3)→(1,4,2,3)→(1,2,4,3)→(2,3,5,3)→(2,3,3,5)
(1,2,2,3)→(1,3,2,3)→(1,4,2,3)→(1,2,4,3)→(2,3,5,3)→(2,3,3,5)
Sample 2 Input
100 100
67 86 61 120 144 138 133 124 37 113 48 25 99 33 99 5 31 80 49 64 56 100 143 114 120 30 131 130 109 8 58 122 37 15 69 140 45 75 66 90 116 68 42 128 129 99 142 87 24 99 120 22 110 123 71 103 110 147 63 141 83 4 129 107 38 91 87 62 133 141 149 73 107 81 22 119 100 61 89 33 97 69 38 38 36 147 82 141 31 95 58 33 108 138 41 124 36 104 95 73
34 63
2 87
15 29
12 84
66 86
21 70
48 66
70 76
79 98
54 56
36 45
58 95
13 46
3 76
14 52
36 46
12 13
68 76
53 97
74 92
36 93
14 20
23 24
11 66
47 91
18 94
1 83
23 96
11 87
44 52
45 74
58 94
44 82
5 23
48 94
53 85
32 67
27 100
52 68
87 89
86 99
34 46
7 82
47 76
43 92
14 77
31 83
17 50
97 98
18 91
8 71
14 51
12 23
5 60
45 68
16 79
5 47
3 80
38 77
53 65
41 51
62 92
80 90
20 83
34 62
32 45
1 19
30 64
16 82
2 2
60 92
23 38
82 92
25 89
11 19
4 38
25 69
30 65
36 43
5 100
11 90
35 56
44 100
60 66
63 98
38 91
36 63
61 63
46 89
28 100
56 58
6 79
56 86
23 100
51 66
24 26
27 93
22 65
58 81
21 38
Sample 2 Output
183 184 184 192 196 205 205 205 205 205 205 205 205 205 205 205 205 205 205 205 210 211 211 211 211 211 211 211 211 211 211 211 211 211 211 211 211 211 210 210 210 210 210 210 210 210 210 210 210 210 210 210 210 210 210 211 211 212 211 211 211 211 212 211 211 211 211 211 211 211 211 211 211 211 211 211 211 211 211 211 211 209 209 209 209 209 209 209 209 209 209 209 209 207 207 207 207 207 207 207