Trong giờ ra chơi, lớp 3A xếp hàng để nhận sữa. Có ~n~ bạn học sinh đứng thành một hàng từ trái sang phải. Trên áo của mỗi bạn có một số nguyên dương. Bạn thứ ~i~ trong hàng hiện tại cho số áo là ~a_i~.

Cô giáo muốn chọn ra một số bạn để tạo thành một hàng thật ngay ngắn. Một hàng được gọi là ngay ngắn nếu số áo của các bạn trong hàng lần lượt là ~1, 2, 3, \ldots~, tức là bắt đầu từ ~1~ và mỗi bạn đứng sau có số áo lớn hơn bạn đứng trước đúng ~1~.

Cô giáo được phép mời một số bạn ra khỏi hàng. Sau khi các bạn đó rời khỏi hàng, những bạn còn lại vẫn giữ nguyên thứ tự như ban đầu.

Yêu cầu. Hãy tìm số bạn ít nhất cần mời ra khỏi hàng để những bạn còn lại tạo thành một hàng ngay ngắn.

Input

Nhập vào từ bàn phím gồm:

• Dòng đầu tiên chứa một số nguyên ~n~ là số bạn học sinh trong hàng ~(1 \leq N \leq 100\, 000)~.
• Dòng thứ hai chứa ~N~ số nguyên ~a_1, a_2, \ldots, a_N~ là số áo của các bạn học sinh ~(1 \leq a_i \leq 100\,000)~

Output

Ghi ra màn hình gồm một dòng duy nhất chứa số bạn ít nhất cần mời ra khỏi hàng.

Sample Input

8
3 1 4 2 7 3 4 5

Sample Output

3

Giải thích

Cô giáo mời các bạn có số thứ tự ~1, 3, 5~ ra khỏi hàng.

Bạn An có một bảng ô vuông gồm ~n~ hàng và ~m~ cột. Các hàng trong bảng được đánh số theo thứ tự từ trên xuống dưới lần lượt là ~1, 2, \ldots, n~. Các cột trong bảng được đánh số theo thứ tự từ trái sang phải lần lượt là ~1, 2, \ldots, m~.

Trong bảng có một kho báu được giấu ở một ô bí mật. An có hai robot để đi tìm kho báu, trong đó:

• Robot A bắt đầu từ ô nằm ở góc trên bên trái, tức là ô nằm ở hàng ~1~, cột ~1~.
• Robot B bắt đầu từ ô nằm ở góc trên bên phải, tức là ô nẳm ở hàng ~1~, cột ~m~.

Ví dụ, đây là bảng ô vuông minh họa khi ~n = 3; m = 5~ và kho báu nằm ở hàng ~2~, cột ~3~:

Trong mỗi phút, một robot có thể đi sang một ô có chung cạnh. Nói cách khác, robot có thể đi lên, đi xuống, đi sang trái hoặc đi sang phải, nhưng không được đi ra ngoài bảng. An biết rằng:

• Robot A cần ít nhất ~S~ phút để đi đến ô có kho báu.
• Robot B cần ít nhất ~T~ phút để đi đến ô có kho báu.

Chú ỷ rằng, kho báu có thể nằm ở vị trí xuất phát ở một trong hai robot.

Yêu cầu. Dựa vào những thông tin được cung cấp, hãy tìm ra vị trí của kho báu

Input

Nhập vào từ bàn phím gồm bốn số nguyên ~n, m, S, T \ (2 \leq n, m \leq 1\,000\,000\,000)~.

Dữ liệu đảm bảo rằng hai số ~S~ và ~T~ luôn phù hợp với một ô nào đó trong bảng.

Output

Ghi ra màn hình gồm một dòng duy nhất chứa hai số nguyên lần lượt là chỉ số hàng và chỉ số cột của ô chứa kho báu

Sample Input

3 5 3 3

Sample Output

2 3

Giải thích

Test ví dụ tương ứng với hình minh họa ở đề bài.

Trong sân trường có một con đường nhỏ đi thẳng từ cổng trường vào lớp học. Dọc theo con đường đó, nhà trường trồng một dãy cột đèn để buổi chiều sân trường sáng hơn. Cột đèn đầu tiên cách cổng trường ~1~ mét. Từ cột đèn thứ hai trở đi, mỗi cột đèn lại cách cổng trường xa hơn cột đứng ngay trước nó đúng ~k~ mét.

Ví dụ nếu ~k = 3~, thì các cột đèn sẽ cách cổng trường lần lượt là ~1~ mét, ~4~ mét, ~7~ mét, ~\ldots~

Vào ngày hội của trường, các bạn học sinh muốn mắc dây ruy băng giữa các cặp cột đèn đứng cạnh nhau. Để tính công việc cho vui, cô giáo đặt ra một quy tắc như sau: Nếu hai cột đèn đang xét cách cổng trường lần lượt là ~x~ mét và ~y~ mét, thì độ khó khi mắc dây giữa hai cột đó có giá trị bằng một phân số có tử số bằng ~1~, mẫu số bằng ~x \times y~.

Yêu cầu. Cho số ~n~ là số cột đèn, tính tổng độ khó để mắc dây giữa các cặp cột đèn liên tiếp. Vì các bạn học sinh mới học các phép toán với phân số, cô giáo mong muốn nhận được kết quả dưới dạng phân số tối giản.

Input

Nhập vào từ bàn phím gồm một dòng chứa hai số nguyên ~n, k \ (n, k \leq 67\,000\,000\,000; n \geq 2; k \geq 1)~.

Output

Ghi ra màn hình gồm kết quả của bài toán theo định dạng sau:

• Nếu đáp án của bài toán là một phân số ~\frac{a}{b}~, hãy in ra kết quả theo định dạng a/b, trong đó phân số phải được đưa về dạng tối giản trước khi in.

Subtasks

• Subtask 1 (40% số điểm). ~n \leq 100~.
• Subtask 2 (60% số điểm). Không có rằng buộc gì thêm.

Sample Input

3 3

Sample Output

2/7

Giải thích

Các cột đèn lần lượt cách cổng trường ~1~ mét, ~4~ mét và ~7~ mét, trong đó

• Độ khó để mắc dây giữa cột đèn thứ nhất và cột đèn thứ hai là ~\frac{1}{1\times 4} = \frac{1}{4}~
• Độ khó để mắc dây giữa cột đèn thứ hai và cột đèn thứ ba là ~\frac{1}{4\times 7} = \frac{1}{28}~

Vì vậy tổng độ khó để mắc dây giữa các cặp cột đèn liên tiếp là: ~\frac{1}{4} + \frac{1}{28} = \frac{8}{28}~, sau khi đưa về phân số tối giản ta có kết quả là ~\frac{2}{7}~.

Trong giờ học Toán, cô giáo viết lên bảng năm số nguyên ~a, b, c, d, k~. Bạn An được chọn một số nguyên ~x~ nằm trong phạm vi từ ~a~ đến ~b~, còn bạn Bình được chọn một số nguyên ~y~ nằm trong phạm vi từ ~c~ đến ~d~.

Cô giáo gọi một cách lựa chọn là may mắn nếu ~x + y~ chia hết cho ~k~. Nhắc lại, ~x + y~ chia hết cho ~k~ nếu khi thực hiện phép chia ~x + y~ cho ~k~, số dư của phép chia là ~0~. Ví dụ

• Nếu ~x = 7; y = 5~ và ~k = 3~ thì ~x + y = 7 + 5 = 12~. Khi chia ~12~ cho ~3~, ta được kết quả là ~4~ dư ~0~, nên cách chọn này là may mắn.
• Ngược lại, nếu ~x = 8; y = 5~ và ~k = 3~ thì ~x + y = 8 + 5 = 13~. Đây không phải là một cách chọn may mắn vì khi chia ~13~ cho ~3~, ta được kết của là ~4~ dư ~1~.

Yêu cầu. Hãy đếm xem có bao nhiều cách lựa chọn hai số ~x~ và ~y~ sao cho cách chọn đó là may mắn.

Input

Nhập vào từ bàn phím gồm một dòng duy nhất chứa năm số nguyên ~a, b, c, d, k \ (1 \leq a,b,c,d,k \leq 1\,000\,000\,000)~

Output

Ghi ra màn hình gồm một dòng duy nhất chứa số cách chọn may mắn.

Subtasks

• Subtask 1 (30% số điểm). ~b - a + 1, d - c + 1 \leq 2000~.
• Subtask 2 (40% số điểm). ~k \leq 2000~.
• Subtask 3 (30% số điểm). Không có rằng buộc gì thêm.

Sample Input

1 4 2 5 3

Sample Output

6

Giải thích

Các cách chọn may mắn là:

• An lựa chọn ~x = 1~ và Bình lựa chọn ~y = 2~. Ta có ~x + y = 1 + 2 = 3~ chia hết cho ~3~.
• An lựa chọn ~x = 1~ và Bình lựa chọn ~y = 5~. Ta có ~x + y = 1 + 5 = 6~ chia hết cho ~3~.
• An lựa chọn ~x = 2~ và Bình lựa chọn ~y = 4~. Ta có ~x + y = 2 + 4 = 6~ chia hết cho ~3~.
• An lựa chọn ~x = 3~ và Bình lựa chọn ~y = 3~. Ta có ~x + y = 3 + 3 = 6~ chia hết cho ~3~.
• An lựa chọn ~x = 4~ và Bình lựa chọn ~y = 2~. Ta có ~x + y = 4 + 2 = 6~ chia hết cho ~3~.
• An lựa chọn ~x = 4~ và Bình lựa chọn ~y = 5~. Ta có ~x + y = 4 + 5 = 9~ chia hết cho ~3~.

Trong lớp có ~N~ bạn học sinh, các bạn được đánh số từ ~1~ đến ~N~. Ban đầu, bạn thứ ~i~ có ~A_i~ viên kẹo. Cô giáo có thể phát thêm kẹo cho các bạn. Cô được phát thêm không quá ~K~ lần. Mỗi lần, cô chọn một bạn bất kỳ. Nếu chọn bạn thứ ~i~, cô sẽ cho bạn đó thêm đúng ~i~ viên kẹo.

Sau khi phát xong, cô giáo nhìn xem bạn có ít kẹo nhất đang có bao nhiêu viên. Cô muốn con số này càng lớn càng tốt, để không bạn nào có quá ít kẹo so với các bạn khác.

Yêu cầu. Hãy tìm số viên kẹo lớn nhất có thể đảm bảo rằng sau khi phát thêm kẹo, bạn nào cũng có ít nhất từng đó viên kẹo.

Input

Nhập vào từ bàn phím gồm:

• Dòng đầu tiên chứa hai số nguyên ~N, K~ là số ban học sinh và số lần phát thêm kẹo tối đa của cô giáo ~(1 \leq N \leq 100\,000; 1 \leq K \leq 1\,000\,000\,000\,000\,000\,000)~
• Dòng thứ hai chứa ~N~ số nguyên ~A_1, A_2, \ldots, A_N~ là số viên kẹo ban đầu của mỗi bạn học sinh ~(1 \leq A_i \leq 1\,000\,000\,000\,000\,000\,000)~

Output

Ghi ra màn hình gồm một dòng duy nhất chứa đáp số của bài toán.

Subtasks

• Subtask 1 (20% số điểm). ~N \leq 2000~ và ~K \leq 2000~.
• Subtask 2 (80% số điểm). Không có rằng buộc gì thêm.

Sample Input

3 3
1 2 3

Sample Output

3

Giải thích

Cô giáo thực hiên những lần phát kẹo như sau:

• Lần phát kẹo đầu tiên, cô giáo phát thêm ~1~ viên kẹo cho bạn thứ nhất. Sau lần phát kẹo này, bạn thứ nhất có ~1 + 1 = 2~ viên kẹo.
• Lần phát kẹo thứ hai, cô giáo phát thêm ~1~ viên kẹo cho bạn thứ nhất. Sau lần phát kẹo này, bạn thứ nhất có ~2 + 1 + 3~ viên kẹo.
• Lần phát kẹo thứ ba, cô giáo phát thêm ~2~ viên kẹo cho bạn thứ hai. Sau lần phát kẹo này, bạn thứ hai có ~2 + 2 = 4~ viên kẹo.

Sau ba lần phát kẹo, số viên kẹo của các bạn học sinh lần lượt là ~3, 4, 3~. Trong đó, bạn học sinh có số viên kẹo nhỏ nhất có ~3~ viên kẹo.