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.|

QBBASE - San nền

Người ta muốn xây dựng một tuyến đường qua một vùng đất. Tuyến đường có chiều dài N và được chia thành N đoạn. Để làm được việc này thì đầu tiên người ta phải san nền cho vùng đất mà tuyến đường sẽ đi qua.

Ban đầu, nền đường tại đoạn thứ i có độ cao là hi và người ta muốn sau khi san nền, tại tất cả các các đoạn đường, nền đường đều có cùng một độ cao là k. Để làm được việc đó thì tại những đoạn mà nền đường có độ cao hi > k người ta cần đào bỏ đi một lượng đất là hi – k và tại những đoạn mà nền đường có độ cao hi < k người ta cần đắp thêm một lượng đất là k – hi. Tổng khối lượng đất đào đắp sẽ là tổng lượng đất phải đào và phải đắp ở N đoạn đường.

Do các kiến trúc sư còn chưa quyết định được về độ cao k cuối cùng của nền đường nên họ yêu cầu bạn viết một chương trình cho họ biết với một số giá trị k nào đó thì tổng khối lượng đất đào đắp sẽ là bao nhiêu.

Đây là 1 bài cơ bản, áp dụng thuật toán tìm kiếm nhị phân.

Input

Dòng đầu tiên 2 ghi số nguyên dương N và M là chiều dài của đoạn đường và số câu hỏi của các kiến trúc sư.

Dòng thứ i trong N dòng tiếp theo ghi số nguyên dương hi là độ cao của nền đường tại đoạn thứ i.

Dòng thứ j trong M dòng cuối ghi số nguyên dương kj là một độ cao của nền đường mà các kiến trúc sư cần tính tổng khối lượng đất đào đắp.

Output

Bạn cần ghi ra M dòng, dòng thứ j ghi tổng khối lượng đất đào đắp ứng với độ cao kj đọc được ở Input.

Example

Input:
4 3
1
3
4
2
1
2
5

Output:
6
4
10

Giới hạn:
1 ≤ N ≤ 10000 
1 ≤ M ≤ 10000
1 ≤ hi ≤ 10000
1 ≤ kj ≤ 10000

Được gửi lên bởi:special_one
Ngày:2008-10-11
Thời gian chạy:1s-2s
Giới hạn mã nguồn:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Ngôn ngữ cho phép:C CSHARP CPP JAVA PAS-FPC

hide comments
2014-11-27 19:40:02 ??? Ares
AC với 0.13s không dùng tknp :)
2014-02-24 15:51:07 kecko
Hinh anh ko lien quan
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.