Mộc Châu là một điểm du lịch nổi tiếng của tỉnh Sơn La với nhiều thắng cảnh đẹp. Đặc biệt, dọc trên trục đường quốc lộ 6 người ta trồng rất nhiều cây đào và mận đan xen nhau. Đến mùa đông, hoa đào đỏ và hoa mận trắng nở xen kẽ nhau rất đẹp. Trên tuyến đường này người ta đếm được có ~N~ cây đào và mận được đánh số từ ~1~ đến ~N~, cây thứ ~i~ người ta đánh giá được có độ đẹp là số nguyên ~A_i\ (1 \le i \le N)~. Rất nhiều du khách đến đây vào mùa hoa đã muốn dùng Flycam để chụp những bức ảnh đẹp. Một bức ảnh đẹp là một bức ảnh chụp được một đoạn liên tiếp các cây đào và mận thỏa mãn:

• Có tối thiểu ~4~ cây.
• Số cây đào và mận bằng nhau.

Độ đẹp của bức ảnh được tính bằng tổng độ đẹp của các cây có trong bức ảnh đó.

Yêu cầu: Hãy tính độ đẹp lớn nhất của bức ảnh có thể chụp được.

Input:

• Dòng đầu chứa số nguyên dương ~N\ (4 \le N \le 3.10^5)~.
• Dòng thứ hai chứa ~N~ số nguyên ~A_1,A_2,\dots,A_N\ (|A_i| \le 10^9, 1 \le i \le N)~

Hai số liên tiếp được ghi cách nhau một dấu cách.

Output:

• Ghi ra một số nguyên duy nhất là độ đẹp lớn nhất của một bức ảnh có thể chụp được.

Sample Input 1

6
-4 3 -2 -6 7 2

Sample Output 1

2

Giải thích:

Chụp 4 cây số ~2, 3, 4, 5~ sẽ có độ đẹp là ~3 + (-2) + (-6) + 7 = 2~

Subtasks:

• Có ~40\%~ số test tương ứng ~40\%~ số điểm có ~N \le 300~
• Có ~40\%~ số test khác tương ứng ~40\%~ số điểm có ~300 < N \le 5000~
• ~20\%~ số test còn lại tương ứng ~20\%~ số điểm có ~5000 < N \le 3.10^5~

Các môn thể thao phối hợp đòi hỏi vận động viên phải có sức mạnh và sự dẻo dai. Câu lạc bộ thể thao của nhà trường có ~n~ bạn tham gia, người thứ ~i\ (1 \le i \le n)~ có sức mạnh ~a_i~ và độ dẻo dai là ~b_i~.

Đội thi đấu có ~k~ người. Trong đội sẽ có một đội trưởng, những người còn lại là thành viên. Tiềm năng của đội được đánh giá bằng tổng sức mạnh của đội trưởng với độ dẻo dai của các thành viên.

Để chuẩn bị đấu giao hữu với trường bạn, huấn luyện viên quyết định sẽ đưa ra đội hình có tiềm năng thấp nhất, chủ yếu là tạo điều kiện cho mọi người có dịp cọ xát với thực tế, đồng thời cũng thử nghiệm các chiến thuật thi đấu.

Ví dụ, với ~n=4~, sức mạnh và độ dẻo dai của mọi người tương ứng là ~A=(3,7,1,6)~ và ~B=(6,3,8,5)~. Nếu ~k=3~ thì để có đội hình tiềm năng thấp nhất cần chọn các người ~2,3,4~ và chỉ định người ~3~ làm đội trưởng. Khi đó tiềm năng của đội sẽ là ~1+3+5=9~.

Do không biết trước lần này cần phải cử bao nhiêu người đi nên huấn luyện viên phải lên phương án cho mọi khả năng với ~k~ từ ~1~ đến ~n~.

Yêu cầu: Hãy đưa ra tiềm năng thấp nhất của đội được cử đi với k lần lượt nhận giá trị từ ~1~ đến ~n~.

Input:

• Dòng đầu tiên chứa số nguyên ~n\ (1 \le n \le 2.10^5)~.
• Dòng thứ ~i~ trong ~n~ dòng sau chứa 2 số nguyên ~a_i~ và ~b_i~ ~(1 \le a_i, b_i \le 10^9; 1 \le i \le n)~.

Output:

• Ghi ra ~n~ số nguyên – các tiềm năng thấp nhất tính được, mỗi số trên một dòng, số thứ ~i\ (1 \le i \le n)~ ứng với trường hợp ~k=i~.

Sample Input 1

4
3 6
7 3
1 8
6 5

Sample Output 1

1
4
9
15

Subtasks:

• Có ~20\%~ số test tương ứng ~20\%~ số điểm có ~N \le 1000~ và ~a_1=a_2=\dots=a_n~
• Có ~20\%~ số test khác tương ứng ~20\%~ số điểm có ~N \le 1000~ và ~b_1=b_2=\dots=b_n~
• Có ~30\%~ số test khác tương ứng ~30\%~ số điểm có ~N \le 5000; a_i,b_i \le 10^6;1 \le i \le n~
• ~30\%~ số test còn lại tương ứng ~30\%~ số điểm không có ràng buộc gì thêm.

Pha lê Swarovski được dùng làm đồ trang sức vô cùng đẹp và vô cùng giá trị. Các hạt pha lê gồm rất nhiều loại khác nhau, mỗi loại được ký hiệu đại diện bởi một số nguyên dương không vượt quá ~10^9~. Trong một lần thám hiểm vùng rừng rậm Amazon, đoàn thám hiểm đã tìm thấy một chuỗi rất dài gồm ~n~ hạt pha lê được gắn liên tiếp nhau. Trước khi đưa về nghiên cứu, người ta quyết định cắt chuỗi hạt tìm thấy thành các chuỗi con gồm các hạt liên tiếp có cùng độ dài. Khi đó độ đa dạng của từng chuỗi hạt là số lượng loại hạt khác nhau tồn tại trong chuỗi hạt đó. Độ đa dạng trong một cách cắt chuỗi ban đầu là độ đa dạng nhỏ nhất của các chuỗi tạo thành.

Yêu cầu: Hãy xác định số lượng cách cắt chuỗi hạt, độ dài chuỗi hạt con và độ đa dạng của từng cách cắt tương ứng.

Input:

Vào từ file văn bản PEARL.INP gồm:

• Dòng đầu tiên chứa số nguyên dương ~n\ (n \le 5.10^5)~ xác định số lượng hạt trong chuỗi ban đầu.
• Dòng thứ hai chứa ~n~ số nguyên dương ~a_1,a_2,a_3,\dots,a_n\ (1 \le i \le n)~ xác định loại của các hạt trong chuỗi theo thứ tự.

Output:

Ghi ra file văn bản PEARL.OUT gồm:

• Dòng đầu chứa số nguyên dương ~k~ – số lượng cách cắt chuỗi ban đầu thành các chuỗi con cùng độ dài.
• ~k~ dòng tiếp theo, dòng thứ ~i\ (1 \le i \le k)~ chứa 2 số nguyên dương ~x_i\ \ y_i~ với ~x_i~ là kích thước các chuỗi con mới theo cách cắt thứ ~i~ và ~y_i~ là độ đa dạng của cách cắt tìm được. Các cách cắt liệt kê theo thứ tự tăng dần của của kích thước chuỗi hạt con.

Ví dụ:

PEARL.INP

6
1 2 2 4 3 3

PEARL.OUT

4
1 1
2 1
3 2
6 4

Subtasks:

• Có ~30\%~ số test tương ứng ~30\%~ số điểm có ~a_1=a_2=\dots=a_n \le 2;\ n \le 100~
• Có ~20\%~ số test khác tương ứng ~20\%~ số điểm có ~a_i \le 2;\ 1 \le i \le n \le 100~
• Có ~20\%~ số test khác tương ứng ~20\%~ số điểm có ~n \le 5.10^4~
• ~30\%~ số test còn lại tương ứng ~30\%~ số điểm không có ràng buộc gì thêm.

Xét dãy số nguyên ~A=(a_1,a_2,\dots,a_n)~. Dãy chứa các phần tử ở các vị trí liên tiếp của ~A~ được gọi là dãy con. Hai dãy con được gọi là khác nhau nếu tồn tại ít nhất một vị trí mà phần tử của ~A~ ở vị trí đó tham gia vào dãy con này và không tham gia vào dãy con kia.

Yêu cầu: Cho số nguyên ~b~. Hãy xác định số lượng dãy con có giá trị lớn nhất của các phần tử trong dãy con đúng bằng ~b~.

Input:

Vào từ file văn bản NUMMAX.INP gồm:

• Dòng đầu tiên chứa hai số nguyên ~n~ và ~b~ ~(2 \le n \le 10^5;\ 1 \le b \le 10^9)~
• Dòng thứ hai chứa ~n~ số nguyên ~a_1,a_2,\dots,a_n~ ~(1 \le a_i \le 10^9;\forall i \in [1;n])~

Output:

Ghi ra file văn bản NUMMAX.OUT một số nguyên duy nhất là số lượng dãy con tìm được.

Ví dụ:

NUMMAX.INP

4 5
1 3 5 2

NUMMAX.OUT

6

Subtask:

• Có ~20\%~ số test tương ứng ~20\%~ số điểm có ~n \le 10^3~ và không có dãy con thỏa mãn.
• Có ~20\%~ số test khác tương ứng ~20\%~ số điểm có ~n \le 10^3~, đồng thời số ~b~ xuất hiện đúng ~1~ lần trong dãy và là số lớn nhất trong dãy đó.
• Có ~20\%~ số test khác tương ứng ~20\%~ số điểm có ~n \le 5.10^3~
• ~40\%~ số test còn lại tương ứng ~40\%~ số điểm không có ràng buộc gì thêm.

Xét bảng hình chữ nhật kích thước ~m \times n~ ô. Các hàng được đánh số từ ~1~ đến ~m~ từ trên xuống dưới, các cột được đánh số từ ~1~ đến ~n~ từ trái qua phải. Ô nằm trên hàng ~i~ và cột ~j~ được ghi một số nguyên không âm ký hiệu ~C_{ij}~. Ở góc trên trái bảng có một quân cờ. Ta phải chuyển quân cờ về ô dưới phải của bảng theo quy tắc sau:

• Tại mỗi bước nhảy, chỉ được di chuyển sang phải trên cùng một hàng hoặc di chuyển xuống dưới theo cùng một cột
• Kích thước bước nhảy không được vượt quá số ghi trên ô có quân cờ hiện tại
• Chỉ được di chuyển trong phạm vi bảng đang xét

Kích thước của bước nhảy từ ô ~(i,j)~ tới ô ~(u,v)~ được tính bằng giá trị ~u+v-i-j~.

Yêu cầu: Cho dãy ~a_1,a_2,\dots,a_m;\ b_1,b_2,\dots,b_n~ và số nguyên dương ~k~. Bảng ~C~ kích thước ~m \times n~ được xác định với ~C_{ij}=1+[(a_i+b_j)\ mod\ k];\ \forall i \in [1;m],\ j \in [1;n]~. Hãy tính số lượng cách di chuyển quân cờ từ ô trên trái ~(1,1)~ xuống ô dưới phải ~(m,n)~.

Input:

Vào từ file văn bản JUMP.INP gồm:

• Dòng đầu chứa ~3~ số nguyên dương ~m, n, k\ (m,n,k \le 4.10^3)~
• Dòng thứ hai chứa ~m~ số nguyên ~a_1,a_2,a_3,\dots,a_m~ ~(0 \le a_i \le 10^9)~
• Dòng thứ ba chứa ~n~ số nguyên ~b_1,b_2,b_3,\dots,b_n~ ~(0 \le b_i \le 10^9)~

Output:

Ghi ra file văn bản JUMP.OUT một số nguyên duy nhất là số cách di chuyển tìm được lấy theo module ~10^9 + 7~.

Ví dụ 1:

JUMP.INP

3 2 1
3 4 11
2 5

JUMP.OUT

3

Ví dụ 2:

JUMP.INP

3 2 2
3 4 11
2 5

JUMP.OUT

4

Subtask:

• ~15\%~ số test tương ứng ~15\%~ số điểm có ~m,n \le 10,\ k=1~
• ~15\%~ số test khác tương ứng ~15\%~ số điểm có ~m,n \le 10^3,\ k=1~
• ~20\%~ số test khác tương ứng ~20\%~ số điểm có ~m,n \le 10^3,\ k \le 10~
• ~20\%~ số test khác tương ứng ~20\%~ số điểm có ~m,n \le 10^3~
• ~30\%~ số test còn lại tương ứng ~30\%~ số điểm không có ràng buộc gì thêm.