Ngày trước, bạn M và người bạn N cùng chuẩn bị một kỳ thi lập trình. Họ nghĩ ra \(n\) bài, đánh số từ \(1\) đến \(n\); chất lượng của bài thứ \(i\) là số nguyên không âm \(a_i\).

Thời gian trôi qua. M không còn là thí sinh Olympic Tin học, nhưng hai người từng hẹn sẽ cùng tổ chức một chuỗi kỳ thi. M chưa quên lời hẹn đó.

M muốn chia \(n\) bài thành một số buổi luyện tập, tức chia dãy bài thành các đoạn liên tiếp. Một cách chia được biểu diễn bởi

Có \(k\) buổi; buổi thứ \(i\) gồm các bài từ \(r_{i-1}+1\) đến \(r_i\).

M nhận thấy chất lượng của một kỳ thi được quyết định bởi bài hay nhất và bài cuối cùng. Vì vậy, chất lượng của một buổi luyện tập được định nghĩa là tích của:

• giá trị \(a_i\) lớn nhất trong buổi;
• giá trị \(a_i\) của bài có chỉ số lớn nhất trong buổi.

M chưa quyết định số buổi và có \(q\) giá trị ứng viên \(k_1,k_2,\ldots,k_q\). Với mỗi \(k_j\), hãy tìm tổng chất lượng lớn nhất của các buổi trong mọi cách chia thành đúng \(k_j\) buổi.

Dữ liệu vào

Dữ liệu gồm nhiều bộ test.

• Dòng đầu chứa số nguyên dương \(t\), số bộ test.
• Với mỗi bộ test:
• Dòng đầu chứa hai số nguyên dương \(n,q\).
• Dòng thứ hai chứa \(n\) số nguyên không âm \(a_1,a_2,\ldots,a_n\).
• Dòng thứ ba chứa \(q\) số nguyên dương \(k_1,k_2,\ldots,k_q\).

Dữ liệu ra

Với mỗi bộ test, in một dòng gồm \(q\) số nguyên không âm. Số thứ \(j\) là tổng chất lượng lớn nhất khi chia thành đúng \(k_j\) buổi.

Ràng buộc

Tính trên toàn bộ các bộ test:

Chấm điểm

Các cột \(\sum n\) và \(\sum q\) được tính trên toàn bộ các bộ test trong một tệp.

Ví dụ

2
4 3
3 2 4 1
3 1 4
5 5
10 3 16 8 7
1 2 3 4 5

26 4 30
112 312 412 469 478

Nguồn

Kỳ thi tập huấn đội tuyển quốc gia Trung Quốc 2026, CCF, giấy phép CC BY-NC.