Cô giáo trường tiểu học \(X\) đang dạy \(n\) học sinh tập xe đạp, các học sinh được đánh số từ \(1\) tới \(n\), học sinh thứ \(𝑗\) có trọng lượng là \(a_𝑗\). Có một xe đạp duy nhất với tải trọng là \(m\), hai học sinh chỉ có thể cùng lên xe nếu tổng trọng lượng của hai học sinh không vượt quá \(m\).

Cô giáo tự hỏi có bao nhiêu cách chọn hai học sinh khác nhau cho cùng lên xe, sau nhiều giờ tính toán không có kết quả, cô quyết định hỏi các chuyên gia lập trình giải bài toán Counting Student Pairs (CSP)

Yêu cầu: Đếm số cặp chỉ số \(i, j\) trong đó \(i < j\) và \(a_i + a_j \leq m\)

Input

• Dòng 1 chứa hai số nguyên dương \(n, m\ (m \leq 10^6)\)
• Dòng 2 chứa \(n\) số nguyên dương \(a_1, a_2, \ldots, a_n\) (\(\forall{i}: a_i \leq 10^6\))

Output

Ghi một số nguyên duy nhất là đáp số

Scoring

• Subtask #1 (\(60\%\) số điểm): \(n \leq 10^4\).
• Subtask #2 (\(20\%\) số điểm): \(n \leq 10^5\).
• Subtask #3 (\(20\%\) số điểm): \(n \leq 10^6\).

Example

5 6
1 2 3 4 5

6

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

Cho một hoá chất chỉ gồm ba nguyên tố C (Carbon), H (Hydrogen) và O (Oxygen) với nguyên tử khối lần lượt là \(12\), \(1\) và \(16\). Hãy tính phân tử khối của hoá chất đó, biết rằng nếu ở dạng nén (ví dụ như O2, (OH)3) thì số lần lặp sẽ trong khoảng \([2, 9]\).

Input

• Một xâu duy nhất chỉ gồm các ký tự C, H, O, (, ) và 2, ..., 9 mô tả hoá chất.

Output

• Một số nguyên duy nhất là phân tử khối của hoá chất. Dữ liệu đảm bảo đáp án không vượt quá \(10^6\).

Scoring

• Subtask \(1\) (\(50\%\) số điểm): Xâu không gồm hai ký tự ( và ).
• Subtask \(2\) (\(50\%\) số điểm): Không có ràng buộc gì thêm.

Example

H2O

18

C3H6O9

186

C(CHO)2(C(OH4)3)5

430