Một dự án phần mềm cần triển khai trong \(𝑛\) tháng đánh số từ 1 tới \(𝑛\). Biết rằng:

• Bắt đầu vào một tháng, dự án có quyền thuê thêm nhân công. Để thuê mỗi nhân công cần một khoản chi phí \(𝐻\) (trả cho nhà tuyển dụng).
• Mỗi nhân công được thuê sẽ được trả một khoản lương \(𝑆\) mỗi tháng kể cả khi không làm việc.
• Kết thúc một tháng, dự án có quyền sa thải nhân công. Để sa thải mỗi nhân công cần trả một khoản chi phí \(𝐷\).
• Không có nhân công nào trước khi dự án bắt đầu. Mỗi tháng \(𝑖\) cần tối thiểu \(𝑎_𝑖\) nhân công. Kết thúc tháng thứ
  \(𝑛\), toàn bộ nhân công phải bị sa thải.

Yêu cầu: Hãy giúp ông giám đốc dự án xây dựng kế hoạch thuê nhân công để dự án được hoàn thành với chi phí
thuê nhân công ít nhất có thể.

Input

• Dòng 1 chứa số tháng \(𝑛\ (1 \leq 𝑛 \leq 4.10^5)\).
• Dòng 2 chứa ba số nguyên dương \(𝐻, 𝑆,𝐷\ (𝐻, 𝑆,𝐷 \leq 10^6)\).
• Dòng 3 chứa \(𝑛\) số nguyên dương \(𝑎_1, 𝑎_2, … , 𝑎_𝑛\) \((\forall 𝑖: 𝑎_𝑖 \leq 10^6)\).

Output

• Dòng 1: Ghi chi phí tối thiểu tìm được
• Ghi \(𝑛\) số, số thứ \(𝑖\) là số nhân công làm trong dự án tại tháng thứ \(i\).

Scoring

• Subtask \(1\) (\(22.5\%\) số điểm): \(𝑛 \leq 400\).
• Subtask \(2\) (\(40\%\) số điểm): \(𝑛 \leq 10^4\).
• Subtask \(3\) (\(37.5\%\) số điểm): \(𝑛 \leq 4 \times 10^5\).

Example

3
4 5 6
10 9 11 

265
10 10 11

Cho một hình chữ nhật có \(N\) hàng và \(M\) cột có số thứ tự được đánh từ trên xuống và từ trái sang phải.

Trên mỗi ô có viết một số nguyên và nhiệm vụ chúng ta phải trả lời \(Q\) truy vấn. Mỗi truy vấn sẽ gồm bốn số nguyên là \(x_1, y_1, x_2, y_2\), sẽ mô tả một khu vực con trong hình chữ nhật. Ứng với mỗi truy vấn, hãy in ra tổng của của khu vực con đó, có điểm \((x_1, y_1)\) là ô góc trái trên và có điểm \((x_2, y_2)\) là ô ở góc phải dưới của khu vực.

Input

• Dòng đầu tiên chứa hai số nguyên \(N\) (chiều rộng) và \(M\) (chiều dài) \((1 \leq N, M \leq 1000)\)
• \(N\) dòng sau, mỗi dòng chứa \(M\) số nguyên, giá trị tuyệt đối của mỗi số nguyên này không vượt quá \(10^9\)
• Dòng kế tiếp, chứa một số nguyên \(Q\) (số truy vấn) \((1 \leq Q \leq 10^5)\)
• \(Q\) dòng kết tiếp, mỗi dòng chứa bốn số nguyên \(x_1, y_1, x_2, y_2\). \((1 \leq x_1 \leq x_2 \leq N)\), \((1 \leq y_1 \leq y_2 \leq M)\)

Output

• In ra \(Q\) dòng, ứng với truy vấn thứ \(i\), in ra một số nguyên là tổng của khu vực hình chữ nhật được nhắc đến bởi truy vấn thứ \(i\).

Example

Test 1

Input

3 3
1 2 3
-4 -5 -6
7 8 9
4
1 1 2 3
2 3 3 3
1 1 2 2
1 1 1 3

Output

-9
3
-6
6

Note

Có \(n\) đứa trẻ muốn đi đến một bánh xe Ferris, và nhiệm vụ của bạn là tìm một chiếc gondola cho mỗi đứa trẻ.

[Chú thích: có khả năng là khu vui chơi nằm ở bên kia dòng sông nên các bạn trẻ cần đi thuyền qua.

Mỗi chiếc gondola có thể có một hoặc hai đứa trẻ trong đó, và ngoài ra, tổng trọng lượng trong một chiếc gondola không được vượt quá \(x\). Bạn biết cân nặng của mỗi đứa trẻ.

Số lượng chiếc gondola tối thiểu cần thiết cho những đứa trẻ là bao nhiêu?

Input

• Dòng đầu vào đầu tiên chứa hai số nguyên \(n\) và \(x\): số lượng đứa trẻ và trọng lượng tối đa cho phép.
• Dòng tiếp theo chứa \(n\) số nguyên \(p_1,p_2,\ldots,p_n\): trọng lượng của mỗi đứa trẻ.

Output

• In một số nguyên: số lượng gondola tối thiểu.

Constraints

• \(1 \leq n \leq 2 \cdot 10 ^ 5\)
• \(1 \leq x \leq 10 ^ 9\)
• \(1 \leq p_i \leq x\)

Example

Sample input

4 10
7 2 3 9

Sample output

3