Vào một ngày đẹp trời, Aquarius đã quyết định gửi một lá thư giao lưu từ Đội tuyển Olympic Tin học IUH đến cho HaUI. Một trận đấu giữa k thành viên của 2 đội.

Danh sách đội tuyển Olympic Tin học IUH có n thành viên . Mỗi thành viên đều có một chỉ số rating-Si

Vì muốn nâng cao sức mạnh của các đội trường mình trước ngày giao đấu, Aquarius đã đề nghị chia các đội thành một nhóm người liên tiếp, không được vượt quá K người, và thành viên của đội này sẽ không là thành viên của đội kia

Biết rằng sau khi chia thành các đội, thì rating của các thành viên trong 1 đội đều sẽ được nâng cao lên bằng với rating của người mạnh nhất trong đội đó

Vì tâm tư, khó tả ngày nhớ đêm mong nên Aquarius không thể tìm được cách chia đội tối ưu. Hãy giúp cậu ấy nhé

Và hãy trả lời tổng lớn nhất các rating sau khi chia một cách tối ưu là bao nhiêu??

VD: xét một dãy gồm 5 thành viên và Aqua chọn số K là 3

[2, 3, 1, 4, 5] sẽ có tổng rating cao nhất là: 21

cách chọn tối ưu là cho 2, 3 vào một đội: tổng rating sẽ là 6

1, 4, 5 vào một đội : tổng rating sẽ là 15

vậy tổng rating cao nhất sẽ là 21

Mô tả đầu vào

Dòng đầu tiên bao gồm 2 số nguyên dương n và k cách nhau bởi 1 dấu cách (1 ≤ k ≤ n ≤~10^{4}~) .

Dòng thứ 2 bao gồm n số nguyên dương là danh sách rating của các bạn Olympic IUH (1 ≤ S[i] ≤ ~10^{9}~).

Mô tả đầu ra

Một số duy nhất là tổng số rating cao nhất thỏa mãn.

Subtask:

20% test: (1 ≤ k ≤ n ≤~10^{1}~)

30% test: (1 ≤ k ≤ n ≤~10^{2}~)

50% test: Không có giới hạn gì thêm

Sample input

5 3
2 3 1 4 5

Sample output

21

Vào một ngày đẹp trời, tienduy nhận được lá thư mời giao đấu của Đội tuyển Olympic Tin học IUH dành cho HaUI. Một trận đấu giữa k thành viên của 2 đội.

Thời gian không còn nhiều, tienduy cần phải chọn đội thi đấu nhanh nhất có thể, anh chàng liền mở danh sách đội lên.

Danh sách đội tuyển Olympic Tin học HaUI có n thành viên. Mỗi thành viên đều có một chỉ số - rating là thang đo khả năng lập trình.

Để không mất nhiều thời gian tienduy quyết định chọn k bạn liên tiếp trong danh sách luôn. Nhưng có một vấn đề anh chàng thấy phân vân, cần chọn đội sao cho vừa mạnh, mọi người trong đội lại vừa ăn ý với nhau. Thế nên tienduy quyết định chọn k bạn liên tiếp có rating trung vị là lớn nhất có thể.

Hãy giúp tienduy chọn đội phù hợp nhé.

Ta định nghĩa: số trung vị của một dãy là số nằm ở chính giữa dãy đó sau khi được sắp xếp tăng dần. Với dãy chẵn phần tử có 2 số nằm ở chính giữa, ta chọn số bên trái. VD: [2, 3, 1, 4, 5] có số trung vị là 3. [3, 2, 4, 1] có số trung vị là 2.

Mô tả đầu vào

Dòng đầu tiên bao gồm 2 số nguyên dương n và k cách nhau bởi 1 dấu cách (1 ≤ k ≤ n).

Dòng thứ 2 bao gồm n số nguyên dương là danh sách rating của các bạn Olympic HaUI (1 ≤ a[i] ≤ ~10^{9}~).

Mô tả đầu ra

Một số duy nhất là số trung vị của nhóm các bạn tienduy chọn để thi đấu thỏa mãn yêu cầu.

Subtask:

10% test: Dãy nhập vào là các số liên tiếp theo thứ tự tăng dần.

20% test: 1 <= a[i] <= 2

30% test: 1 <= N <= 5000.

40% test: Không có giới hạn gì thêm

Sample input

4 3
3 2 1 4

Sample output

2

Giải thích: tienduy có 2 cách chọn đội là [3, 2, 1] và [2, 1, 4]. Ở cả 2 cách này đều có rating trung vị là 2.

Mô tả vấn đề

Bạn có một dãy liên tiếp gồm n phần tử, và Q truy vấn từ L đến R.

Gọi d là độ dại từ đoạn con từ L đến R

Liệu trên đoạn con từ L đến R có tồn tại số nguyên x xuất hiện nhiều hơn d/2 lần, (biết d/2 là phép chia nguyên).

Nếu câu trả lời có tồn tại hãy in YES ngược lại NO

Mô tả đầu vào

N, Q *: Trong đó *N là độ dài mảng, Q là số lượng truy vấn 1 ≤ N, Q≤ ~10^{5}~

dòng tiếp theo là các phần tử ai trong mảng N, 1 ≤ ai≤ N

Q dòng tiếp theo gồm hai số L và R

1 ≤ L ≤R ≤ N

Mô tả đầu ra

Tương ứng với mỗi Q hãy xuất ra YES hoặc NO

Subtask:

10% test: 1<= N,Q <=100

30% test: 1 <= N,Q <= 5000

60% test: Không có giới hạn gì thêm

Sample Input 1

4 3
1 2 3 3
1 3
2 4
1 4

Sample Output 1

NO
YES
NO

Sample Input 2

4 2
1 2 3 3
1 1
3 4

Sample Output 2

YES
YES

Mô tả vấn đề

cho hai số A và B, bạn có biết a+b bằng mấy?

Mô tả đầu vào

A, B

0 ≤ B ≤ A ≤ ~10^{1000}~

Mô tả đầu ra

Hãy xuất ra một giá trị là kết quả A+B

Subtask:

10% test: 0 ≤ B ≤ A ≤ ~10^{9}~

20% test: 0 ≤ B ≤ A ≤ ~10^{20}~

70% test: Không có giới hạn gì thêm

Sample Input 1

1 1

Sample Output 1

2