Cho dãy số nguyên \(A\) gồm \(N\) phần tử \(𝐴_1, 𝐴_2, ... , 𝐴_𝑁\) và một số nguyên \(𝑇\). Tìm bộ ba số \(𝑎_𝑖, 𝑎_𝑗, 𝑎_𝑘\) \((1 \leq 𝑖 < 𝑗 < 𝑘 \leq 𝑁)\) có chênh lệch giữa trung bình cộng của ba số này và \(𝑇\) là nhỏ nhất. Nếu có nhiều bộ có cùng chênh lệch, hãy chọn một bộ số có tổng lớn nhất.

Input

• Dòng đầu tiên gồm hai số nguyên \(𝑁\) và \(𝑇\) \((3 \leq 𝑁 \leq 5000, |𝑇| \leq 10^9)\).
• Dòng thứ hai gồm \(𝑁\) số nguyên \(𝐴_1, 𝐴_2, ... , 𝐴_𝑁\) \((|A_𝑖| \leq 10^9, 1 \leq 𝑖 \leq 𝑁)\).

Output

• Một dòng gồm một số nguyên duy nhất là tổng của ba số tìm được.

Scoring

• Subtask \(1\) (\(40\%\) số điểm): \(𝑁 \leq 10\);
• Subtask \(2\) (\(30\%\) số điểm): \(𝑁 \leq 100\);
• Subtask \(3\) (\(30\%\) số điểm): Không có ràng buộc gì thêm.

Example

4 0
-2 3 1 0

1

Bạn được cho hai số nguyên \(n\) và \(k\).

Yêu cầu: Bạn hãy tính số cách chia \(n\) viên kẹo giống nhau cho \(k\) người khác nhau sao cho mỗi người đều có ít nhất \(1\) viên kẹo.

Hai cách được xem là khác nhau khi một người bất kỳ có số kẹo trong cách này khác với trong cách kia.

Input

• Chứa số hai số nguyên \(n\) và \(k\) \((1 \le k \le n \le 10^6)\).

Output

• Chứa một số nguyên là đáp án của bài toán khi chia lấy dư cho \(10^9 + 7\).

Example

6 2

5

Cho mảng \(A\) gồm \(N\) số nguyên. Nhiệm vụ của bạn là sắp xếp mảng theo số lần xuất hiện các phần tử của mảng. Số xuất hiện nhiều lần nhất đứng trước. Nếu hai phần tử có số lần xuất hiện như nhau, số nhỏ hơn đứng trước. Ví dụ \(A = {5, 5, 4, 6, 4 }\), ta nhận được kết quả là \(A[] = {4, 4, 5, 5, 6}\).

Input

• Dòng đầu tiên đưa vào số lượng bộ test \(T\) (\(1 \leq T \leq 100\)).
• Những dòng kế tiếp đưa vào \(T\) bộ test. Mỗi bộ test gồm hai dòng:
  • Dòng đầu tiên đưa vào \(N\) (\(1 \leq N \leq 10^4\)), tương ứng với số phần tử của mảng \(A\);
  • Dòng tiếp theo là \(N\) số \(A_i\) (\(1 \leq i \leq N, 1 \leq A_i \leq 10^5\)); các số được viết cách nhau một vài khoảng trống.

Output

• Đưa ra kết quả mỗi test theo từng dòng.

Example

2
5
5 5 4 6 4
5
9 9 9 2 5

4 4 5 5 6 
9 9 9 2 5 

Cho \(n\) số \(a_1, a_2, ..., a_n\) \((1 \le n, a_i \le 10^5)\), và \(q\) \((1 \le q \le 10^5)\) truy vấn. Mỗi truy vấn là hai số \(l, r\), bạn cần tính:

Input

• Dòng đầu tiên là hai số \(n\) và \(q\).
• Dòng tiếp theo là \(n\) số \(a_1, a_2, ..., a_n\).
• \(q\) dòng cuối cùng, mỗi dòng là hai số \(l, r\) thể hiện một truy vấn.

Output

• \(q\) dòng là đáp án các truy vấn.

5 2
1 2 3 4 5
1 3
2 5

14
40