FOS Class 09 Contest 01 - Bộ đề bài - LQDOJ: Le Quy Don Online Judge

#	Bài tập	Điểm	Thời gian:	Giới hạn bộ nhớ
1	Trung bình cộng	100 (p)	1.0s	256M
2	Chia kẹo 1	100 (p)	1.0s	256M
3	Sắp xếp theo tần suất	100 (p)	1.0s	256M
4	Tổng của tích	100 (p)	1.0s	256M

1. Trung bình cộng

Điểm: 100 (p) Thời gian: 1.0s Bộ nhớ: 256M Input: bàn phím Output: màn hình

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

Test 1

Input

4 0
-2 3 1 0

Output

Note

Trung bình cộng của các bộ $3$ số là:
$(−2, 3, 1)$ ∶ $0.666$
$(−2, 3, 0)$ ∶ $0.333$
$(−2, 1, 0)$ ∶ $−0.333$
$(3, 1, 0)$ ∶ $1.333$
Bộ ba số thoả mãn là: $(−2, 3, 0)$

2. Chia kẹo 1

Điểm: 100 (p) Thời gian: 1.0s Bộ nhớ: 256M Input: bàn phím Output: màn hình

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

Test 1

Input

6 2

Output

3. Sắp xếp theo tần suất

Điểm: 100 (p) Thời gian: 1.0s Bộ nhớ: 256M Input: bàn phím Output: màn hình

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

Test 1

Input

Output

4 4 5 5 6 
9 9 9 2 5

4. Tổng của tích

Điểm: 100 (p) Thời gian: 1.0s Bộ nhớ: 256M Input: bàn phím Output: màn hình

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:

$1 \times a_l + 2 \times a_{l + 1} + ... + (r - l + 1) \times a_r$

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.

Example

Input

Output

14
40