Một dãy gồm n số nguyên không âm a1, a2,...., an được viết thành một hàng ngang, giữa hai số liên tiếp có một khoảng trắng, như vậy có tất cả (n-1) khoảng trắng. Người ta muốn đặt k dấu cộng và (n-1-k) dấu trừ vào (n-1) khoảng trằng đó để nhận được một biểu thức có giá trị lớn nhất. Ví dụ, với dãy gồm 5 số nguyên 28, 9, 5, 1, 69 và k = 2 thì cách đặt 28+9-5-1 +69 là biểu thức có giá trị lớn nhất. Yêu cầu: Cho dãy gồm n số nguyên không âm a1, a2..., an và số nguyên dương k, hãy tìm cách đặt k dấu cộng và (n-1-k) dấu trừ vào (n-1) khoảng trắng để nhận được một biểu thức có giá trị lớn nhất.

Đầu vào: Dòng đầu chứa hai số nguyên dương n, k; Dòng thứ hai chứa n số nguyên không âm a1, a2,..., an;

Ràng buộc: 1 <= k < n ≤ 10^5; 0 <= a[i] ≤ 10^6

In ra giá trị lớn nhất của biểu thức

Input:

5 3
10 1 3 9 8

Output:

29

Cho mảng A gồm n các số nguyên dương. Bạn hãy thực hiện các thao tác sau đây:

• Sắp xếp các phần tử trong mảng A theo tần suất giảm dần, nếu 2 số có cùng tần suất thì số nào nhỏ hơn sẽ sắp xếp lên trước

• Sắp xếp các phần tử trong mảng A theo tần suất giảm dần, nếu 2 số có cùng tần suất thì số nào xuất hiện trước sẽ in ra trước

Ràng buộc: 1 <= n <= 10^5; 0 <= A[i] <= 10^6

Input:

10
6 8 4 10 3 4 10 2 4 1

Output:

4 4 4 10 10 1 2 3 6 8 
4 4 4 10 10 6 8 3 2 1

Cho 2 dãy A và B đã sắp xếp tăng dần. Bạn hãy thực hiện trộn 2 dãy A và B thành 1 dãy C cũng sắp xếp tăng dần.

Ràng buộc: Ràng buộc: ~1 \leq N \leq 2.10^6~; ~-10^6 \leq A[i], B[i] \leq 10^6~

Input:

5
1 3 5 6 9
3
2 7 8

Output:

1 2 3 5 6 7 8 9