Chiến Lược Tối Ưu Điểm Số

Bối cảnh

Bạn có một mảng \( A = [A_1, A_2, \ldots, A_N] \) gồm N số nguyên.

Yêu cầu

Với một tham số cố định K \((1 \leq K \leq N)\), bạn thực hiện quy trình sau:

1. Bắt đầu với điểm số bằng 0.
2. Có một danh sách, ban đầu chứa các phần tử \( A_1, A_2, \ldots, A_{K-1} \).
3. Với mỗi i từ K đến N :
   • Thêm A_i vào danh sách.
   • Sau đó, chọn một phần tử từ danh sách, cộng nó vào điểm số của bạn, và loại bỏ nó khỏi danh sách.
4. Bạn muốn tối ưu hóa điểm số của mình.

Tìm điểm số tối đa có thể đạt được cho mỗi giá trị K = 1, 2, 3, ..., N nếu thực hiện quy trình này một cách tối ưu.

Input

Dòng đầu tiên chứa một số nguyên T , biểu thị số lượng test case.

Mỗi test case bao gồm hai dòng:

• Dòng đầu tiên chứa một số nguyên N , độ dài của mảng.
• Dòng thứ hai chứa N số nguyên cách nhau bởi khoảng trắng — \( A_1, A_2, \ldots, A_N \).

Output

Với mỗi test case, xuất trên một dòng mới N số nguyên cách nhau bởi khoảng trắng. Số nguyên thứ i là kết quả cho K = i .

Ràng buộc

\( 1 \leq T \leq 10^4 \)

\( 1 \leq N \leq 2 \cdot 10^5 \)

\( 1 \leq A_i \leq 10^9 \) Tổng N trên tất cả các test case không vượt quá \( 2 \cdot 10^5 \).

Ví dụ 1

Input

3
2
1 24
4
5 8 3 2
5
10 21 32 43 54

Output

25 24
18 16 13 8
160 150 129 97 54

Giải thích ví dụ

• Test case 1: Quy trình như sau:

  • Với K = 1 , ban đầu danh sách là rỗng.

    • Với i = 1 , chèn \(A_1 = 1 \) vào danh sách. Chỉ có thể chọn 1 . Điểm số là 1.
    • Với i = 2 , chèn \(A_2 = 24 \) vào danh sách. Chỉ có thể chọn 4 . Điểm số là 1 + 24 = 25 .

  • Với K = 2 , ban đầu danh sách chứa \(A_1 = 1 \).

    • Với i = 2 , chèn 24 vào danh sách. Chọn 24 . Điểm số là 24 .

Thông tin học tập

• Buổi: B17
• Concepts: sorting, prefix sums
• Giới hạn kiến thức: B01-B17
• Time limit: 2 seconds
• Memory limit: 64 MB
• Point: 25