Cho dãy ~a~ nguyên dương gồm ~n~ phần tử. Ta định nghĩa hàm ~f(l,r)~ như sau: ~f(l,r) = 1\times a[l] + 2\times a[l+1] + 3\times a[l+2] + ... (r-l+1)\times a[r]~.

Có ~q~ truy vấn, mỗi truy vấn gồm hai số ~l~, ~r~ với ~1 \le l \le r \le n~. Với mỗi truy vấn, hãy in ra ~f(l,r)~.

Input

• Dòng đầu gồm 2 số nguyên dương ~n~ và ~q~. ~(1 \le n, q \le 10^5)~
• Dòng thứ hai gồm ~n~ số nguyên dương miêu tả dãy ~a~. ~(1 \le a[i] \le 10^5)~.
• ~q~ dòng tiếp theo, mỗi dòng gồm 2 số nguyên dương ~l~, ~r~ miêu tả các truy vấn.

Ouput

• In ra ~q~ dòng, mỗi dòng là kết quả của một truy vấn tương ứng.

Subtask

• Subtask ~1~: ~n,q \le 2 \times 10^3~ ~(30\%)~
• Subtask ~2~: Trong tất cả các truy vấn, ~l=1~.
• Subtask ~3~: Không giới hạn gì thêm ~(40\%)~.

Sample Test

Input

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

Output

5
8
30

Cho một xâu ~s~ có độ dài ~n~ chỉ bao gồm các kí tự ~a,b,c~. Một đoạn ~[l,r]~ được gọi là tốt khi và chỉ khi có một kí tự trong đoạn có số lần xuất hiện lớn hơn một nửa độ dài đoạn. Nói cách khác, gọi ~cnt(d,l,r)~ là số lần xuất hiện của kí tự ~d~ trong đoạn ~[l,r]~, ta cần tồn tại một kí tự ~d~ trong đoạn ~[l,r]~ sao cho ~cnt(d,l,r) > (r-l+1)/2~. (Với ~d~ thuộc ~[a,b,c]~)

Hãy in ra độ dài đoạn tốt lớn nhất.

Input

• Dòng đầu gồm số nguyên dương ~n~ miêu tả độ dài xâu. ~(1 \le n \le 10^5)~
• Dòng thứ hai miêu tả xâu ~s~. Xâu ~s~ chỉ bao gồm các kí tự ~a,b,c~ và có độ dài ~n~.

• Ouput

• In ra độ dài đoạn tốt lớn nhất.

Sample Test

Input

7
aabbbcc

Output

5

Giải thích: Chọn đoạn ~[1,5]~.

Cho dãy ~a~ gồm ~n~ số nguyên dương. Bạn được chọn đúng ~k~ cặp số bằng các thao tác, mỗi thao tác có thể chọn một trong các cách sau:

• 1) Chọn ~2~ số đầu hàng.

• 2) Chọn ~2~ số cuối hàng.

• 3) Chọn ~1~ số đầu hàng và ~1~ số cuối hàng.

• 4) Loại ~1~ số đầu hàng ra khỏi hàng.

• 5) Loại ~1~ số cuối hàng ra khỏi hàng.

Sau mỗi thao tác, nếu bạn chọn thao tác ~1~, ~2~, ~3~ thì sẽ được cộng thêm số điểm bằng giá trị tuyệt đối của ~2~ số bạn chọn, đồng thời loại ~2~ số đó ra khỏi hàng và được tính là chọn 1 cặp số. Ngược lại với thao tác ~4~ và ~5~, bạn không được tính là chọn một cặp số.

Hãy tìm cách thực hiện đúng ~k~ thao tác để đem về số điểm là cao nhất. Biết ban đầu bạn có số điểm bằng 0.

Input

• Dòng đầu gồm ~2~ số nguyên dương ~n~ và ~k~ ~(2*k \le n)~
• Dòng sau gồm ~n~ số nguyên dương miêu tả dãy ~a~. ~(1 \le a_i \le 10^9)~

Ouput

• In ra một số nguyên duy nhất là số điểm lớn nhất có thể thu về sau khi thực hiện đúng ~k~ thao tác.

Subtask

• Có 40% test thỏa mãn điều kiện: ~n \le 300~, ~k \le 2~.
• Có 40% test thỏa mãn điều kiện: ~n \le 30, 2*k = n~.
• Có 20% test thỏa mãn điều kiện: ~n \le 300~

Sample Test

Input

6 2
1 3 10 2 1 4

Output

12

Giải thích:

• Thao tác ~1~: Chọn ~2~ thẻ cuối hàng và được cộng ~|4-1| = 3~ điểm.
• Thao tác ~2~: Loại thẻ ở cuối hàng có giá trị bằng ~2~.
• Thao tác ~3~: Chọn một thẻ ở đầu hàng và một thẻ ở cuối hàng, thu được thêm ~|10-1| = 9~ điểm.
• Tổng cộng sẽ được ~2~ cặp số tương ứng ~12~ điểm.

Cho dãy ~a~ gồm ~n~ phần tử nguyên và một số nguyên dương ~k~. Hãy in ra đoạn con liên tiếp có tổng lớn thứ ~k~. (Có ~n*(n+1)/2~ đoạn con liên tiếp trong dãy).

Input

• Dòng đầu gồm 2 số nguyên dương ~n~ ~(1 \le n \le 10^5)~ và ~k~ ~(1 \le k \le n*(n+1)/2)~.
• Dòng thứ 2 gồm ~n~ số nguyên miêu tả dãy ~a~. ~(-10^9 \le a_i \le 10^9)~.

Ouput

• In ra giá trị của đoạn con liên tiếp có tổng lớn thứ ~k~.

Sample Test

Input

4 3
1 -1 2 -2

Output

1

Giải thích: đoạn con ~[1,3], [3,3]~ là hai đoạn con có giá trị lớn nhất với tổng bằng ~2~. Tiếp đến là hai đoạn con ~[1,1], [2,3]~ có tổng bằng ~1~ có giá trị lớn thứ ~3~ và ~4~. Vậy đoạn con có giá trị lớn thứ ~k~ sẽ có giá trị bằng ~1~.

Reimu cần phong ấn một cuốn sách. Cô có ~n~ lá bùa, trên lá bùa thứ ~i~ có số nguyên dương ~a_i~. Để phong ấn cuốn sách cô cần chọn một số lá bùa trong số ~n~ lá bùa sao cho tích của chúng kết thúc bằng chữ số ~d~ và để đạt được hiệu quả cao thì tích phải là lớn nhất có thể. Bạn hãy giúp cô tìm ra những lá bùa cần sử dụng nhé!

Input

• Dòng đầu gồm 2 số nguyên dương ~n, d (1 \le n \le 100000, 0 \le d \le 9).~
• Dòng tiếp theo gồm ~n~ số nguyên dương ~a_i~.

Output

• Dòng đầu tiên là số tự nhiên ~k~ là số lượng lá bùa được chọn hoặc không có cách chọn in ra ~-1~.
• Nếu có cách chọn thì dòng tiếp theo số trên những lá bùa được chọn (có thể theo thứ tự ngẫu nhiên).

Sample Test

Input:

6 3
8 9 4 17 11 5

Output:

3
9 11 17 

Cho mảng ~a~ có ~n~ phần tử, có thể thực hiện thao tác sau vô số lần: Chọn chỉ số ~1 \le i \le n - 1~ sao cho ~a_i = a_{i + 1}~ và xóa 2 phần tử ~i~ và ~i + 1~ thay thế chúng bằng phần tử có giá trị ~a_i + 1~. Hỏi độ dài nhỏ nhất có thể của mảng ~a~ là bao nhiêu.

Input

• Dòng đầu tiên gồm số tự nhiên ~n \le 500~.
• Dòng tiếp theo gồm ~n~ số tự nhiên của mảng ~a~ và ~\le 1000~.

Output

• Độ dài nhỏ nhất có thể của mảng ~a~.

Sample Test

Input:

7
3 3 4 4 4 3 3

Output:

2