Cho một dãy ~a~ gồm ~n~ phần tử nguyên.

Hãy tìm đoạn con liên tiếp có tổng lớn nhất của dãy

Input

• Dòng đầu tiên chứa số nguyên dương ~n~.
• Dòng thứ hai gồm ~n~ số nguyên miêu tả dãy ~a~.

Output

• In ra giá trị thỏa mãn.

Điều kiện

• ~1 \le n \le 2*10^5~.
• ~|a| \le 10^6~.

Subtask

• ~50\%~ số điểm: ~n \le 1000~.
• ~50\%~ số điểm: ~n \le 2*10^5~.

Ví dụ

Input 1:

4
3 -2 4 -1

Output 1:

5

Cho bảng ~a~ có kích thước ~n \times m~.

Hãy tìm một hình chữ nhật con có tổng lớn nhất trong bảng.

Input

• Dòng đầu tiên chứa ba số nguyên dương ~n,m~.
• ~n~ dòng sau, mỗi dòng gồm ~m~ số nguyên miêu tả bảng ~a~.

Output

• In ra tổng lớn nhất tìm được.

Điều kiện

• ~1 \le n,m \le 400~.
• ~|a_{i,j}| \le 10^5~

Subtask

• ~50\%~ số điểm: ~n,m \le 40~
• ~50\%~ số điểm: ~n,m \le 400~.

Ví dụ

Input 1:

4 5
1 -2 3 4 -5
-3 2 1 -4 1
1 -3 2 -3 1
1 -2 -3 -4 -1

Output 1:

7

Trên trục số ~Ox~, cho ~𝑁~ đoạn thẳng, mỗi đoạn thẳng được xác định bởi hai điểm đầu và cuối là hai số nguyên. Một điểm ~𝑀~ được gọi là nằm trong đoạn thẳng ~𝐴𝐵~ nếu ~𝐴 ≤ 𝑀 ≤ 𝐵~.

Yêu cầu: Đếm xem có bao nhiêu điểm có toạ độ nguyên nằm trong đúng ~𝐾~ đoạn thẳng.

Dữ liệu nhập vào từ file văn bản DC.INP:

• Dòng đầu tiên gồm hai số nguyên ~𝑁~ và ~𝐾~ ~(1 ≤ 𝐾 ≤ 𝑁 ≤ 10^5);~
• ~𝑁~ dòng sau, mỗi dòng gồm hai số nguyên ~𝑎, 𝑏~ mô tả hai điểm đầu và cuối của đoạn thẳng ~(1 ≤ 𝑎 ≤ 𝑏 ≤ 10^{18})~.

Kết quả ghi ra file văn bản DC.OUT:

Một số nguyên duy nhất là số lượng điểm có toạ độ nguyên nằm trong đúng ~𝐾~ đoạn thẳng.

Ràng buộc

• Có ~50\%~ số test ứng với ~50\%~ số điểm của bài thoả mãn: ~𝑎, 𝑏 ≤ 10^3;~
• ~30\%~ số test khác ứng với ~30\%~ số điểm của bài thoả mãn: ~𝐾 = 𝑁;~
• ~20\%~ số test còn lại ứng với ~20\%~ số điểm của bài không có ràng buộc gì thêm.

Ví dụ

Input

3 2
1 5
2 8
3 7

Output

3

Giải thích: Toạ độ của ~3~ điểm nằm trong đúng ~2~ đoạn thẳng là: ~2, 6, 7~.

• Điểm có toạ độ ~2~ nằm trong ~2~ đoạn thẳng: đầu tiên và thứ hai.
• Điểm có toạ độ ~6, 7~ nằm trong ~2~ đoạn thẳng: thứ hai và thứ ba.

Input

3 1
1 5
2 8
3 7

Output

2   

Giải thích: Toạ độ của ~2~ điểm nằm trong đúng ~1~ đoạn thẳng là: ~1, 8~.

• Điểm có toạ độ ~1~ chỉ nằm trong đoạn thẳng đầu tiên.
• Điểm có toạ độ ~8~ chỉ nằm trong đoạn thẳng thứ ba.

Input

3 3
1 5
2 8
3 7

Output

3

Giải thích: Toạ độ của ~3~ điểm nằm trong cả ~3~ đoạn thẳng là: ~3,4,5~.

Cho dãy số gồm ~n~ số nguyên ~a_1, a_2, …, a_n~ và ~2~ số nguyên không âm ~L, R (L ≤ R)~.

Yêu cầu: Đếm số cặp ~(i, j)~ thỏa mãn điều kiện: ~i ≤ j~ và ~L ≤ |a_i+…+a_j| ≤ R~.

Input

• Dòng đầu tiên chứa ~3~ số nguyên ~n, L, R~ ~(n ≤ 3*10^5 ; 0 ≤ L ≤ R ≤ 10^9)~
• Dòng thứ hai chứa ~n~ số nguyên ~a_1, a_2,…, a_n (|a_i|≤ 10^9)~

Output

• Một số nguyên duy nhất là số lượng cặp ~(i, j)~ đếm được.

Subtask

• Subtask 1 (~30\%~ số điểm): ~n \le 10^3~.
• Subtask 2 (~50\%~ số điểm): ~n \le 10^5~ và ~a_i \ge 0~.
• Subtask 3 (~20\%~ số điểm): Không có giới hạn gì thêm.

Sample Test

Input

3 0 1
1 -1 2

Output

4

Cho bảng ~a~ có kích thước ~n \times m~. Có ~q~ truy vấn, mỗi truy vấn có dạng: ~(x,y,u,v)~, yêu cầu in ra tổng của hình chữ nhật có ô trái trên là ~(x,y)~ và ô phải dưới là ~(u,v)~ của bảng.

Input

• Dòng đầu tiên chứa ba số nguyên dương ~n,m,q~.
• ~n~ dòng sau, mỗi dòng gồm ~m~ số nguyên miêu tả bảng ~a~.
• ~q~ dòng sau, mỗi dòng gồm ~4~ số nguyên dương ~x,y,u,v~ miêu tả truy vấn.

Output

• Với mỗi truy vấn, in ra tổng của hình chữ nhật con cần tính.

Điều kiện

• ~1 \le n,m \le 500~.
• ~1 \le q \le 10^5~.
• ~1 \le x \le u \le n~
• ~1 \le y \le v \le m~.
• ~1 \le a_{i,j} \le 500~

Subtask

• ~50\%~ số điểm: ~q \le 100~
• ~50\%~ số điểm: ~q \le 10^5~.

Ví dụ

Input 1:

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

Output 1:

18
3
6
8

Cấu trúc dữ liệu là nội dung rất quan trọng trong khoa học máy tính. Trong chương trình giảng dạy cho các lớp chuyên Tin, nội dung cấu trúc dữ liệu được đưa vào nhiều chuyên đề. Một bài toán thao tác trên bảng được dùng để kiểm tra khả năng tổ chức dữ liệu và linh hoạt trong xử lí như sau: Cho một bảng số gồm ~m~ hàng và ~n~ cột, các hàng được đánh số từ trên xuống dưới từ ~1~ đến ~m~, , các cột được đánh số từ trái sang phải từ ~1~ đến ~n~, ô nằm giao giữa hàng ~i~ ~(1 \le i \le m)~ và cột ~j~ ~(1 \le j \le n)~ gọi là ô ~(i,j)~ và có giá trị ban đầu là ~a_{i,j}~. Cần thực hiện ~Q~ thao tác trên bảng số, mỗi thao tác thuộc một trong hai loại:

• Thao tác loại ~1~ có dạng: ~1~ ~x~ ~y~ ~u~ ~v~ ~w~ có nghĩa là với mỗi ô nằm trong hình chữ nhật có ô trái trên là ô ~(x,y)~ và ô phải dưới là ô ~(u,v)~ sẽ được cộng thêm ~w~.
• Thao tác loại ~2~ có dạng: ~2~ ~x~ ~y~ ~u~ ~v~ có nghĩa là cần đưa ra tổng giá trị của các ô nằm trong hình chữ nhật có ô trái trên là ô ~(x,y)~ và ô phải dưới là ô ~(u,v)~.

Input

• Dòng đầu tiên chứa ba số nguyên dương ~m,n,Q~ ~ (1 \le m,n \le 500)~.
• Dòng thứ ~i~ ~(1 \le i \le m)~ trong ~m~ dòng sau chứa ~n~ số nguyên không âm ~a_{i,1},a_{i,2},...,a_{i,n}~ ~(a_{i,j} \le 10^9)~.
• Dòng thứ ~k~ ~(1 \le k \le Q)~ trong ~Q~ dòng sau mô tả thao tác thứ ~k~:
  • Nếu là thao tác loại ~1~, gồm một dòng sáu số nguyên ~1,x,y,u,v,w~ ~(1 \le x \le u \le m; 1 \le y \le v \le n; 0 \le w \le 10^9)~
  • Nếu là thao tác loại ~2~, gồm một dòng năm số nguyên ~2,x,y,u,v~ ~(1 \le x \le u \le m; 1 \le y \le v \le n)~

Output

• Với mỗi truy vấn loại ~2~, in ra kết quả truy vấn đó.

Subtask

• ~30\%~ số điểm: ~Q \le 100~
• ~30\%~ số điểm: ~Q \le 10^5~ và tất cả thao tác loại ~1~ xuất hiện trước thao tác loại ~2~.
• ~20\%~ số điểm: ~Q \le 10^4~
• ~20\%~ số điểm: ~Q \le 10^5~

Ví dụ

Input 1:

2 3 3
0 0 0
0 0 0
2 1 1 2 3
1 1 1 2 3 1
2 1 1 2 2      

Output 1:

0
4