Một trò chơi điện tử được thiết kế cho phép người chơi sử dụng nhiều tuyệt chiêu. Hệ thống sẽ lưu giữ quá trình sử dụng tuyệt chiêu của người chơi bằng một dãy ~n~ các số nguyên dương ~a_1, a_2, ..., a_i, ..., a_n~ (~a_i~ là mã số của tuyệt chiêu mà người chơi đã sử dụng ở lượt thứ ~i~).

Trò chơi có quy định là khi một tuyệt chiêu được sử dụng ở lượt chơi thứ ~i~, thì người chơi chỉ có thể sử dụng lại tuyệt chiêu đó từ lượt chơi thứ ~i + k~ trở đi.

Yêu cầu

Hãy viết chương trình kiểm tra việc sử dụng các tuyệt chiêu của người chơi.

Input

Vào từ file văn bản TUYETCHIEU.INP gồm 2 dòng:

• Dòng đầu chứa ~2~ số nguyên dương ~n~ và ~k~ (~1 \leq n \leq 10^6~, ~1 \leq k \leq 10^4~)

• Dòng tiếp theo gồm ~n~ số nguyên dương ~a_1~, ~a_2~, ~a_3~, ..., ~a_n~ (~a_i \leq 10^6~, ~1 \leq i \leq n~).

Các số trên cùng một dòng các nhau một khoảng trắng.

Output

Ghi ra file văn bản TUYETCHIEU.OUT một số nguyên duy nhất cho biết tuyệt chiêu nào đã sử dụng vi phạm quy định. Nếu có nhiều hơn một tuyệt chiêu vi phạm, thì ghi tuyệt chiêu vi phạm có mã nhỏ nhất. Nếu người chơi không vi phạm, thì ghi ~-1~.

Scoring

Sample Input 1

6 3
9 9 3 1 4 1

Sample Output 1

1

Sample Input 2

5 2
1 2 3 1 3

Sample Output 2

-1

Trong một trò chơi xây địa hình 2D, một khu vực A gồm ~n~ vùng liên tiếp có độ cao lần lượt là ~A_1, A_2, ..., A_n~.

Khu vực ~A~ được gọi là một ngọn núi khi sườn bên trái của nó tăng đơn điệu và sườn bên phải của nó giảm đơn điệu. Nghĩa là, khi A là ngọn núi với đỉnh núi là vùng có chiều cao ~A_x~, thì ~n~ vùng của ~A~ phải có độ cao đảm bảo ~A_1<A_2<...<A_x~ và ~A_x>...>A_{n-1}>A_n~. (~1 < x < n~). Hai vùng đầu tiên và cuối cùng của khu vực A không được là đỉnh núi.

Yêu cầu

Hãy viết chương trình tính chi phí tối thiểu để đắp khu vực A thành một ngọn núi.

Input

Vào từ file văn bản DAPNUI.INP gồm hai dòng:

• Dòng đầu chứa số nguyên n (~3 \leq n \leq 10^5~)

• Dòng tiếp theo gồm ~n~ số nguyên ~A_1, A_2, ..., A_n~ (~0 \leq A_i \leq 10^9~, ~1 \leq i \leq n~).

Các số trên cùng một dòng cách nhau một khoảng trắng.

Output

Ghi ra file văn bản DAPNUI.OUT một số nguyên duy nhất cho biết chi phí tối thiểu để đắp khu vực A thành một ngọn núi.

Scoring

Sample Input 1

5
1 1 1 1 1

Sample Output 1

4

Sample Input 2

6
3 4 5 6 5 1

Sample Output 2

0

LƯU Ý: Đội ngũ TGB quyết định sửa giới hạn của ~m~ thành ~2 \times 10^5~, khác với đề gốc (để phù hợp với kích thước dữ liệu nhập vào trên TGBOJ).

Trên một vùng núi, người dân tự thiết kế mô hình xử lý nước uống cho các hộ dân vùng cao. Họ đặt hệ thống lưu giữ nước từ các nguồn trên cao dổ về. Lượng nước đưa vào ~n~ hệ thống làn lượt là ~a_1, a_2, ..., a_n~ (lít).

Các hệ thống có cấu tạo giống nhau. Mỗi hệ thống có ~m~ bồn chứ nước được đánh số từ ~1, 2, ..., m~ với dung tích lần lượt là ~r_1, r_2, ..., r_m~ (lít). Bồn chứa nước số ~1~ được đặt ở vị trí cao nhất, tiếp đến là bồn số ~2~, ... và thấp nhất là bồn số ~m~. Do đó, khi nước vào hệ thống, nước sẽ chảy vào bồn số ~1~ trước, chỉ khi nào đầy bồn số ~1~, nước mới chảy tiếp qua bồn số ~2~, tương tự đến bồn số ~m~.

Đồng thời, họ xây dựng ~m~ máy xử lý nước uống. Sau khi các hệ thống đã lưu giữ nước vào các bồn chứa. Máy xử lý nước số ~1~ sẽ sử lý nước từ các bồn chứa số ~1~ của tất cả các hệ thống lưu giữ. Tương tự cho các máy xử lý nước còn lại.

Yêu cầu

Hãy viết chương trình tính lượng nước thu được trong từng máy xử lý nước.

Input

Vào từ file văn bản LOCNUOC.INP gồm ~3~ dòng:

• Dòng đầu chứa hai số nguyên ~n~ và ~m~ (~1 \leq n \leq 2 \cdot 10^5~, ~1 \leq m \leq 2 \cdot 10^5~).

• Dòng thứ hai gồm ~n~ số nguyên ~a_1, a_2, ..., a_n~ (~1 \leq a_i \leq 10^5~, ~1 \leq i \leq n~).

• Dòng thứ ba gồm ~m~ số nguyên ~r_1, r_2, ..., r_n~ (~1 \leq r_i \leq 10^5~, ~1 \leq i \leq m~).

Các số trên cùng một dòng cách nhu một khoảng trắng.

Output

Ghi ra file văn bản LOCNUOC.OUT một dòng duy nhất gồm tối đa ~m~ số nguyên dương là lượng nước thu được ở từng máy xử lý nước. Nếu máy xử lý nước không nhận được nước thì không in ra. Các số trên cùng một dòng cách nhau một khoảng trắng.

Scoring

Sample Input 1

4 5
6 8 2 5
4 3 2 7 6

Sample Output 1

14 6 1