Nhà trường tổ chức Hội chợ xuân kéo dài trong 7 ngày, giá thuê một gian hàng là ~K~ đồng/ngày. Lớp An có ~N~ đồng, muốn thuê một gian hàng trong 7 ngày để bán thiệp. Hỏi số tiền còn lại sau khi thuê gian hàng của lớp An là bao nhiêu?

Input

• Dòng đầu tiên chứa một số nguyên dương ~N~ (~N ≤ 10^9~) là số tiền lớp An có.
• Dòng thứ hai chứa một số nguyên dương ~K~ (~K ≤ 10^9~) là giá thuê gian hàng trong một ngày.

Output

Một số nguyên là số tiền còn lại của lớp An. Nếu không đủ tiền thuê trong 7 ngày thì ghi ra ~-1~.

Sample Input 1

1000000
50000

Sample Output 1

650000

Sample Input 2

350000
50000

Sample Output 2

0

Sample Input 3

200000
50000

Sample Output 3

-1

Cho dãy số nguyên ~A~ gồm ~N~ phần tử phân biệt ~A_1, A_2, ..., A_N~ và số nguyên dương ~K~. Phần tử ~A_i~ được gọi là cân bằng K nếu trong dãy xuất hiện phần tử có giá trị bằng ~A_i + K~ và ~A_i - K~.

Ví dụ dãy số ~5, 2, 4, 6~ và ~K = 1~ thì có 1 phần tử cân bằng là ~5~ vì dãy số có phần tử là ~5 - 1 = 4~ và ~5 + 1 = 6~.

Yêu cầu: Đếm số lượng phần tử cân bằng K của dãy số ~A~.

Input

• Dòng đầu tiên chứa hai số nguyên dương ~N~ và ~K~ (~N ≤ 10^5~; ~K ≤ 10^9~).
• Dòng thứ hai chứa ~N~ số nguyên ~A_1, A_2, ..., A_N~ (~|A_i| ≤ 10^9~; ~1 ≤ i ≤ N~).

Output

Gồm một số nguyên là kết quả của bài toán.

Sample Input 1

6 1
4 1 7 8 5 6

Sample Output 1

3

Sample Input 2

6 2
4 -1 7 8 5 6

Sample Output 2

1

Subtasks

Điền 26 kí tự Tiếng Anh in thường theo thứ tự từ điển thành một vòng tròn cách đều nhau 1 đơn vị.

Khoảng cách giữa hai kí tự là số bước di chuyển ngắn nhất từ kí tự này đến kí tự kia. Ví dụ khoảng cách giữa hai kí tự a và c là 2; khoảng cách giữa a và z là 1.

Khoảng cách của một xâu là khoảng cách lớn nhất giữa hai kí tự bất kì của xâu đó. Ví dụ tính khoảng cách của xâu adc:

• Khoảng cách của a và d là 3.
• Khoảng cách của a và c là 2.
• Khoảng cách của d và c là 1.

Vậy khoảng cách của xâu adc là ~max(3, 2, 1) = 3~.

Cho xâu ~S~ gồm ~N~ kí tự được đánh chỉ số từ 1 đến ~N~ và ~Q~ truy vấn, mỗi truy vấn yêu cầu tính khoảng cách của xâu con từ vị trí ~L~ đến vị trí ~R~ trong xâu ~S~ (~1 ≤ L ≤ R ≤ N~).

Input

• Dòng đầu tiên chứa xâu ~S~ chỉ gồm các kí tự Tiếng Anh in thường gồm ~N~ kí tự (~1 ≤ N ≤ 10^5~).
• Dòng thứ hai chứa số nguyên dương ~Q~ (~Q ≤ 10^5~).
• ~Q~ dòng tiếp theo, mỗi dòng gồm hai số nguyên ~L~, ~R~ (~1 ≤ L ≤ R ≤ N~) mô tả đoạn con của xâu ~S~ cần tính khoảng cách.

Output

Gồm ~Q~ dòng, mỗi dòng gồm một số nguyên là kết quả của truy vấn tương ứng.

Sample Input 1

abcyzz
3
1 3
2 5
5 6

Sample Output 1

2
4
0

Subtasks

Cho dãy số nguyên ~A~ gồm ~N~ phần tử ~A_1, A_2, ..., A_N~ và số nguyên ~S~. Bạn có thể xóa đi một đoạn con liên tiếp bất kì trong dãy (tức là chọn hai chỉ số ~L~, ~R~ với ~1 ≤ L ≤ R ≤ N~ và xóa các phần tử ~A_L, A_{L+1}, ..., A_R~). Quy ước: Nếu xóa hết dãy thì tổng còn lại bằng ~0~.

Yêu cầu: Tìm độ dài nhỏ nhất của đoạn con cần xóa sao cho tổng các phần tử còn lại của dãy không vượt quá ~S~. Nếu không cần xóa đoạn nào thì kết quả là ~0~, nếu không có cách xóa thỏa mãn thì kết quả là ~-1~.

Input

• Dòng đầu tiên chứa số nguyên dương ~N~ (~N ≤ 10^5~).
• Dòng thứ hai chứa ~N~ số nguyên ~A_1, A_2, ..., A_N~ (~|A_i| ≤ 10^9~; ~1 ≤ i ≤ N~).
• Dòng thứ ba chứa số nguyên ~S~ (~|S| ≤ 10^{14}~).

Output

Gồm một số nguyên là kết quả của bài toán.

Sample Input 1

5
4 -5 4 4 -2
0

Sample Output 1

2

Sample Input 2

3
4 2 1
0

Sample Output 2

3

Sample Input 3

3
1 2 3
-2

Sample Output 3

-1

Sample Input 4

3
1 2 0
5

Sample Output 4

0

Subtasks

• Có 40% số test ứng với 40% số điểm có ~N ≤ 100~; ~A_i ≥ 0~.
• 20% số test tiếp theo ứng với 20% số điểm có ~N ≤ 5000~; ~A_i ≥ 0~.
• 20% số test tiếp theo ứng với 20% số điểm có ~A_i ≥ 0~.
• 20% số test còn lại ứng với 20% số điểm không có ràng buộc gì thêm.

Trong một buổi tập bắn súng, có ~N~ tấm bia được xếp thành một hàng dọc, đánh số từ 1 tới ~N~. Độ bền của các tấm bia được mô tả bởi dãy số ~A~, tấm bia thứ ~i~ có độ bền ban đầu là ~A_i~.

Một tấm bia được coi là bị phá hủy nếu độ bền của nó giảm xuống nhỏ hơn hoặc bằng ~0~ (khi này coi độ bền của tấm bia là ~0~).

Xạ thủ được quyền chọn một loại đạn có sức công phá ~X~ (với ~X~ là số nguyên dương tùy ý) để sử dụng cho toàn bộ buổi tập. Mỗi lần bắn, xạ thủ bắn một viên đạn thẳng dọc theo hàng các tấm bia, viên đạn sẽ trúng tấm bia đầu tiên chưa bị phá hủy (tấm bia thứ ~i~ có chỉ số nhỏ nhất và độ bền ~A_i > 0~).

Do đạn có tính xuyên phá nên sẽ gây ảnh hưởng lên tấm bia thứ ~i~ và các tấm bia thứ ~j~ phía sau nó (~j ≥ i~). Độ bền của tấm bia thứ ~j~ (~i ≤ j ≤ N~) bị giảm một lượng theo công thức: ~max(0, X - (j - i)^2)~.

Ví dụ: với ~X = 5~, có 6 tấm bia với độ bền lần lượt là ~[0, 2, 5, 0, 1, 2]~, viên đạn đầu tiên trúng vào tấm bia thứ ~2~, sẽ gây ảnh hưởng cho các tấm bia thứ ~2, 3, 5, 6~ (vì tấm bia 1 và 4 có độ bền bằng 0), độ bền của các tấm bia bị giảm được tính như sau:

• Tấm bia thứ ~2~: ~max(0, 5 - (2 - 2)^2) = max(0, 5 - 0^2) = 5~.
• Tấm bia thứ ~3~: ~max(0, 5 - (3 - 2)^2) = max(0, 5 - 1^2) = 4~.
• Tấm bia thứ ~5~: ~max(0, 5 - (5 - 2)^2) = max(0, 5 - 3^2) = 0~.
• Tấm bia thứ ~6~: ~max(0, 5 - (6 - 2)^2) = max(0, 5 - 4^2) = 0~.

Vậy sau lượt bắn này, độ bền của các tấm bia là ~[0, 0, 1, 0, 1, 2]~.

Yêu cầu: Hãy tìm giá trị sức công phá ~X~ nhỏ nhất sao cho xạ thủ có thể phá hủy toàn bộ các tấm bia khi bắn không quá ~K~ lần.

Input

• Dòng đầu chứa hai số nguyên dương ~N~, ~K~ (~N ≤ 2 × 10^5~; ~K ≤ 10^9~) tương ứng là số tấm bia và số lần bắn tối đa.
• Dòng tiếp theo chứa ~N~ số nguyên dương mô tả dãy ~A~ (~A_i ≤ 10^9~; ~1 ≤ i ≤ N~).

Output

Gồm một số nguyên dương ~X~ nhỏ nhất tìm được.

Sample Input 1

6 3
6 7 1 3 2 1

Sample Output 1

5

Sample Input 2

3 1
3 7 3

Sample Output 2

8

Subtasks

• Có 30% số test ứng với 30% số điểm có ~N, K ≤ 30~; ~A_i ≤ 30~.
• 20% số test tiếp theo ứng với 20% số điểm có ~K = 1~.
• 30% số test tiếp theo ứng với 30% số điểm có ~N ≤ 1000~.
• 20% số test còn lại với 20% số điểm không có ràng buộc gì thêm.