Một tối mưa phùn, một con cú đưa thư đậu lên bậu cửa sổ và thả xuống một phong thư niêm phong bằng nến sáp to bản. Trên sáp in hình một ngôi sao tám cánh: dấu hiệu của Học viện Pháp Thuật nội trú.

Khi con cú rời đi, một tiếng chuông chợt vang lên trong không gian tĩnh lặng: Đã đến thời điểm Kỳ Khảo Thí Cốc Sao Băng chính thức bắt đầu.

Trong học viện tồn tại những pháp bảo cao giai: cầu thang tự xoay, hành lang tự đổi hướng, chân dung biết nói và những bí mật nằm trong các căn phòng cấm.
Harry Potter học viên năm thứ nhất cùng với đồng đội phải vượt qua các thử thách. Mỗi phòng là một câu thần chú phép thuật.

Harry bước vào Sảnh Cầu Thang Xoay. Trên từng bậc đá đặt một viên Linh Thạch. Có ~N~ viên, đánh số từ ~1~ đến ~N~. Mỗi Linh Thạch chứa một lượng pháp lực ~a_i~. Có viên tỏa ra ánh sáng rực đỏ, có viên lạnh buốt.

Trên trần treo một chiếc Trống Chu Kỳ gõ theo nhịp ~K~. Khi Harry chạm vào một đoạn Linh Thạch liên tiếp ~[l, r]~, tổng pháp lực của đoạn đó cộng lại.
Cửa chỉ mở nếu tổng pháp lực đó khớp nhịp trống, tức là chia hết cho ~K~.

Harry cần đếm tất cả các đoạn liên tiếp có thể mở cửa. Hãy trợ giúp Harry qua ải đầu tiên này.

Dữ liệu

• Dòng 1: Hai số nguyên ~N~ và ~K~
• Dòng 2: ~N~ số nguyên ~a_1, a_2, \dots, a_N~

Kết quả

• In ra một số nguyên: Số đoạn con thỏa mãn điều kiện

Ví dụ

Input

5 3
1 2 3 4 1

Output

4

Giải thích

Có đúng ~4~ đoạn con có tổng chia hết cho ~3~:

• ~[1,2]~ có tổng ~1+2=3~
• ~[1,3]~ có tổng ~1+2+3=6~
• ~[3,3]~ có tổng ~3~
• ~[2,4]~ có tổng ~2+3+4=9~

Ràng buộc

• ~1 \le N \le 2 \cdot 10^5~
• ~1 \le K \le 10^9~
• ~|a_i| \le 10^9~
• Các số trên cùng một dòng cách nhau ít nhất bởi một dấu cách

Chấm điểm

• Subtask1 ~(33.33\%)~ số điểm: ~N \le 2000~
• Subtask2 ~(33.33\%)~ số điểm: ~K \le 2 \cdot 10^5~
• Subtask3 ~(33.34\%)~ số điểm: Không có ràng buộc bổ sung

Harry đã vượt qua cầu thang tự xoay và tiến hành đột nhập vào Thư Viện Chân Dung. Trên bàn đá là một dải mật mã ấn ký tạo thành xâu ~S~. Mỗi ký tự là một ấn nhỏ, nhưng muốn mở cửa, Harry phải gom đủ Ngũ Ấn Chủ: ~a~, ~e~, ~i~, ~o~, ~u~.

Chân dung canh cửa nói rằng Ngũ Ấn không phân biệt áo choàng hay áo sơ mi. Harry phải tìm đoạn liên tiếp ngắn nhất trong ~S~ chứa đủ cả 5 ấn chủ.

Hãy giúp Harry tìm ra khóa ngũ ấn thủ này.

Dữ liệu

• Dòng 1: Xâu ~S~

Kết quả

• In ra một số nguyên: độ dài nhỏ nhất, hoặc ~-1~ nếu không thể tìm thấy.

Ví dụ

Input

bAxxeiiOouZ

Output

8

Giải thích

Xâu con từ vị trí ~2~ đến ~9~ là AxxeiiOo, trong đó có đủ ~a~, ~e~, ~i~, ~o~, ~u~ theo quy tắc không phân biệt hoa thường.
Độ dài là ~8~. Không có đoạn ngắn hơn thỏa đủ cả 5 ấn chủ.

Ràng buộc

• ~1 \le |S| \le 2 \cdot 10^5~

Chấm điểm

• Subtask1 ~(40\%)~ số điểm: ~|S| \le 5000~
• Subtask2 ~(60\%)~ số điểm: Không có ràng buộc bổ sung

Sang phòng thứ ba, Harry tới Nhà Kho Chổi Bay. Ở đây có ~N~ bầu dược liệu, xếp thành một hàng. Bầu thứ ~i~ có khối lượng đúng bằng ~a_i~. Vì là dược liệu tinh khiết, nên ~a_i~ luôn dương.

Có đúng ~K~ xe đẩy phép thuật. Mỗi xe phải chở một đoạn bầu liên tiếp và mọi bầu đều phải được chở. Cây cầu gỗ cũ cuối kho chỉ chịu được xe nặng nhất. Muốn cả đoàn qua cầu, Harry phải chia sao cho xe nặng nhất nhẹ nhất có thể.

Yêu cầu

Cho dãy số nguyên dương ~a_1, a_2, \dots, a_N~. Hãy chia dãy thành đúng ~K~ đoạn con liên tiếp không rỗng. Gọi tổng mỗi đoạn là ~\text{sum}_1, \text{sum}_2, \dots, \text{sum}_K~.

Hãy tìm giá trị nhỏ nhất có thể của: ~\max(\text{sum}_1, \text{sum}_2, \dots, \text{sum}_K)~.

Dữ liệu

• Dòng 1: hai số nguyên ~N~ và ~K~
• Dòng 2: ~N~ số nguyên dương ~a_1, a_2, \dots, a_N~

Kết quả

• In ra một số nguyên: giá trị nhỏ nhất của tổng đoạn lớn nhất

Ví dụ

Input

5 2
7 2 5 10 8

Output

18

Ràng buộc

• ~1 \le K \le N \le 2 \cdot 10^5~
• ~1 \le a_i \le 10^9~

Chấm điểm

• Subtask 1 ~(40\%~ số điểm: ~N \le 2000~
• Subtask 2 ~(60\%~ số điểm: Không có ràng buộc bổ sung

Phòng cuối cùng là Khu Vườn Cấm. Mặt đất là một dải ô sáng từ ~1~ đến ~N~, mỗi ô là một mảnh tinh quang. Mảnh thứ ~i~ chứa năng lượng ~a_i~. Có mảnh rực rỡ (dương), có mảnh lạnh giá hút năng lượng (âm).

Harry phải thực hiện đúng ~K~ lần Thu Hoạch. Mỗi lần Thu Hoạch là chọn một đoạn liên tiếp và gom trọn năng lượng của đoạn đó.

Luật khu vườn:

• Các đoạn Thu Hoạch không được chồng lấn, tức là không dùng lại cùng một ô.
• Mỗi đoạn phải có độ dài nằm trong ~[L, R]~.

Harry cần chọn để tổng năng lượng thu được là lớn nhất. Đây là ải khó nhất của Cốc Sao Băng.

Yêu cầu

Cho dãy số nguyên ~a_1, a_2, \dots, a_N~. Hãy chọn đúng ~K~ đoạn con liên tiếp, đôi một không giao nhau, sao cho mỗi đoạn có độ dài trong ~[L, R]~.
Mục tiêu là tổng các phần tử thuộc ~K~ đoạn đã chọn là lớn nhất có thể.

Dữ liệu

• Dòng 1: Bốn số nguyên ~N~, ~K~, ~L~, ~R~
• Dòng 2: ~N~ số nguyên ~a_1, a_2, \dots, a_N~

Kết quả

• In ra một số nguyên: tổng lớn nhất khi chọn đúng ~K~ đoạn

Ví dụ

Input

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

Output

10

Giải thích

Với input:

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

Ta có:

• ~N=8~, ~K=2~, ~L=2~, ~R=3~
• Mỗi lần Thu Hoạch phải chọn một đoạn liên tiếp có độ dài 2 hoặc 3
• Hai đoạn không giao nhau nghĩa là không dùng chung vị trí nào (tập chỉ số rời nhau).

Một cách chọn hợp lệ:

Chọn đoạn ~[3,4]~

• Độ dài: ~4-3+1 = 2~ (nằm trong ~[L,R]=[2,3]~)
• Tổng: ~a_3+a_4 = 3+4 = 7~

Chọn đoạn ~[6,8]~

• Độ dài: ~8-6+1 = 3~ (nằm trong ~[2,3]~)
• Tổng: ~a_6+a_7+a_8 = 2+(-5)+6 = 3~

Kiểm tra không giao nhau

• ~[3,4]~ dùng các vị trí ~{3,4}~
• ~[6,8]~ dùng các vị trí ~{6,7,8}~
• Hai tập này giao nhau rỗng ⇒ không giao nhau (hợp lệ).

Tổng năng lượng thu được:

• ~7 + 3 = 10~

Ràng buộc

• ~1 \le N \le 2 \cdot 10^5~
• ~1 \le K \le 20~
• ~1 \le L \le R \le N~
• ~|a_i| \le 10^9~
• Luôn tồn tại cách chọn đủ ~K~ đoạn thỏa ràng buộc

Chấm điểm

• Subtask1 ~25\%~ số điểm: ~N \le 5000~
• Subtask2 ~25\%~ số điểm: ~R-L \le 50~
• Subtask3 ~50\%~ số điểm: Không có ràng buộc bổ sung