Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

P182SUMG - ROUND 2G - Kỹ thuật vun đống

Có n đống đá có cỡ lần lượt là a[1], a[2], .. a[n].

Trong một lần di chuyển bạn có thể lấy một đống này dồn tất cả vào đống khác. Khi thêm đống i vào đống j, cỡ của đống j tăng theo cỡ đống i hiện tại và đống i hết sạch (cỡ bằng không). Chi phí cho một lần di chuyển bằng với cỡ của đống được thêm vào.

Tuy nhiên một điều kiện đặt ra là chỉ được thêm vào một đống không quá k lần (sau đó chỉ có thể đem đống đó đi dồn vào đống khác).

Yêu cầu tìm chi phí tối thiểu để dồn tất cả các đống thành một đống với k cho trước.

Input

Dòng đầu tiên là số nguyên n – số đống đá (1 ≤ n ≤ 105).

Dòng thứ hai gồm n số nguyên là số lượng đá trong mỗi đống a[1], a[2], .. a[n] (1 ≤ a[i] ≤ 109).

Dòng thứ ba là số nguyên q – số lượng truy vấn cho k (1 ≤ q ≤ 105).

Dòng thứ tư bao gồm q số nguyên là q truy vấn (q giá trị k) – k[1], k[2] ,.. k[q] (1≤ k[i] ≤105).

Output

Một dòng duy nhất gồm q số nguyên là chi phí tối thiểu cho mỗi truy vấn k[i].

Example

Input:
5
2 3 4 1 1
2
2 3

Output:
9 8

Giải thích

Trong truy vấn k= 2 : một cách để có chi phí tối thiểu là lấy đống 4 và đống 5 dồn vào đống 2 (chi phí 2x1 = 2) được [2,5,4,0,0] lấy đống 1 dồn vào đống 3 chi phí 2 được [0,5,6,0,0], cuối cùng lấy đống 2 dồn vào đống 3 chi phí 5 và kết thúc , tổng chi phí là 2 × 1 + 2 + 5 = 9.

Được gửi lên bởi:adm
Ngày:2018-07-13
Thời gian chạy:1s
Giới hạn mã nguồn:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Ngôn ngữ cho phép:ASM32-GCC ASM32 ASM64 MAWK BC C CSHARP C++ 4.3.2 CPP CPP14 COFFEE LISP sbcl DART FORTH GO JAVA JS-RHINO JS-MONKEY KTLN OCT PAS-GPC PAS-FPC PERL PERL6 PROLOG PYTHON PYTHON3 PY_NBC R RACKET SQLITE SWIFT UNLAMBDA

© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.