Cho một dãy số nguyên ~a~ gồm ~n~ ~(1 \le n \le 10^5, 1 \le a_i \le 10^6)~ phần tử và ~q~ ~(1 \le q \le 10^5)~ truy vấn. Mỗi truy vấn có dạng ~l,r~, hãy in ra tổng ~a_l,a_{l+1},..,a_r~.

Input

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

Output

3
5
15
7

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

Hãy đếm số đoạn con liên tiếp ~[l,r]~ của dãy ~a~ sao cho tổng của đoạn con đó bằng độ dài của đoạn, hay ~a_l + a_{l+1} + ... + a_r = r - l + 1~.

Input

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

Output

• In ra số đoạn con thỏa mãn.

Điều kiện

• ~1 \le n \le 2*10^5~.
• ~0 \le a \le 9~.

Subtask

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

Ví dụ

Input 1:

3
1 2 0

Output 1:

3

Input 2:

5
1 1 0 1 1 

Output 2:

6

Do đã quá quen với dãy fibonacci, hôm nay, chúng ta hãy cùng tìm hiểu về dãy tribonacci.

Số tribonacci thứ ~i~ sẽ có công thức truy hồi như sau: ~f[i] = f[i-1] + f[i-2] + f[i-3]~ nếu ~i > 3~, ngược lại ~f[i] = i~ nếu ~i \le 3~.

Cho ~n~ số tribonacci đầu tiên và một số ~k~ (~k \le n~), hay tìm một dãy con bất kì (không nhất thiết phải liên tiếp) của dãy ~n~ số tribonacci này sao cho tổng của các phần tử trong dãy con đó chia hết cho ~k~.

Input

• Gồm một dòng chứa số nguyên dương ~n~ và số nguyên dương ~k~ ~(1 \le k \le n \le 10^5)~

Output

• Dòng đầu in ra số ~q~ là độ dài của dãy con thỏa mãn tìm được, nếu không tồn tại in ra ~-1~.
• Dòng thứ hai in ra ~q~ chỉ số của dãy con tìm được.
• Nếu có nhiều hơn một dãy con thỏa mãn, in ra bất kì kết quả nào.

Subtask

• ~30\%~ số test có ~n \le 20~.
• ~40\%~ số test có ~n \le 2000~.
• ~30\%~ số test còn lại có ~n \le 10^5~.

Sample Test

Input:

5 4

Output:

2
2 4

Giải thích:

• ~5~ phần tử đầu tiên của dãy tribonacci là: 1 2 3 6 11

• Chọn ra phần tử thứ ~2~ và ~4~ có tổng bằng: ~2+6 = 8~ chia hết cho ~4~.

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

Ngày hôm nay có ~n~ gian hàng bán đồ ăn tại lễ hội ở đền Hakurei. Yuyuko ham ăn muốn đi ăn ~q~ lượt, mỗi lượt từ gian hàng ~l~ đến gian hàng ~r~. Với mỗi gian hàng, hãy in ra số lần cô ghé thăm.

Input

• Dòng đầu gồm 2 số ~n, q~.
• ~q~ dòng tiếp theo mỗi dòng thứ ~i~ gồm 2 số ~l_i, r_i~ ~(1 \le l_i \le r_i \le 10^5)~ là lượt đi ăn thứ ~i~.

Output

• In ra ~n~ số ứng với ~n~ cửa hàng là số lần Yuyuko vào gian hàng.

Sample Test

Input:

4 3
1 3
2 4
1 2

Output:

2 3 2 1

Cho một dãy ~a~ gồm ~n~ phần tử nguyên không âm và ~q~ thao tác, thao tác thứ ~i~ có dạng ~(l_i,r_i,d_i)~, nghĩa là tăng giá trị của các phần tử trong mảng ~a~ từ vị trí ~l_i~ tới ~r_i~ thêm ~d_i~ đơn vị.

Bạn cần thực hiện ~k~ truy vấn, truy vấn thứ ~i~ có dạng ~(x_i,y_i)~, có nghĩa là thực hiện các thao tác ~x_i,x_{i+1},...,y_i~.

Hãy in ra giá trị của các phần tử trong mảng ~a~ sau khi thực hiện ~k~ truy vấn.

Input

• Dòng đầu tiên chứa ~3~ số nguyên dương ~n,q,k~.
• Dòng thứ hai gồm ~n~ số nguyên không âm miêu tả dãy ~a~.
• ~q~ dòng sau, dòng thứ ~i~ gồm ~3~ số nguyên dương ~l_i,r_i,d_i~ miêu tả thao tác thứ ~i~.
• ~k~ dòng sau, dòng thứ ~i~ gồm ~2~ số nguyên dương ~x_i,y_i~ miêu tả truy vấn thứ ~i~.

Output

• Gồm một dòng in ra ~n~ số, số thứ ~i~ là giá trị của phần tử ~a_i~ sau khi thực hiện ~k~ truy vấn.

Điều kiện

• ~1 \le n \le 10^5~.
• ~0 \le a_i,d_i \le 10^5~.

Subtask

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

Ví dụ

Input 1:

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

Output 1:

9 18 17

Input 2:

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

Output 2:

5 18 31 20

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 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

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

Có ~q~ truy vấn, mỗi truy vấn có dạng ~l,r,d~, có nghĩa là tăng phần tử thứ ~l~ lên ~d~ đơn vị, phần tử thứ ~l+1~ lên ~2*d~ đơn vị, ..., phần tử thứ ~r~ lên ~(r-l+1)*d~ đơn vị. Nói cách khác, phần tử thứ ~i \in [l,r]~ sẽ được tăng thêm ~(i-l+1)*d~ đơn vị.

Hãy in ra dãy ~a~ sau khi thực hiện đủ ~q~ truy vấn.

Input

• Dòng đầu tiên chứa số nguyên dương ~n~
• Dòng thứ hai gồm ~n~ số nguyên không âm miêu tả dãy ~a~.
• ~q~ dòng sau, mỗi dòng gồm ~3~ số nguyên ~(l,r,d)~ miêu tả truy vấn.

Output

• Gồm một dòng in ra ~n~ số, số thứ ~i~ là giá trị của phần tử ~a_i~ sau khi thực hiện ~q~ truy vấn.

Điều kiện

• ~1 \le n,q \le 10^6~.
• ~0 \le a_i,d_i \le 10^5~.

Subtask

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

Ví dụ

Input 1:

1
10
3
1 1 40
1 1 0
1 1 -15

Output 1:

35 

Input 2:

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

Output 2:

5 9 13 20 25 

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

Đất nước Mirinda tươi đẹp được mô tả bằng một ma trận ~n \times m~ ô vuông, ô ở dòng thứ ~i~ từ trên xuống và cột thứ ~j~ từ trái sang gọi là ô ~(i, j)~. Khoảng cách giữa ô ~(x,y)~ với ô ~(i,j)~ là ~|x - i| + |y - j|~. Ô ~(i, j)~ có giá trị tài sản là ~a_{i,j}~.

Do biến đổi khí hậu, những cơn bão ngày một nhiều hơn và mạnh hơn. Mỗi cơn bão được đặc trưng bởi:

• ~w~ - cấp bão,
• ~R_1~ - bán kính bão,
• ~R_2~ - bán kính mắt bão,
• ~(x, y)~ - tọa độ bão sẽ đổ bộ.

Theo đó, các ô ~(i, j)~ có khoảng cách đến ô ~(x, y)~ thuộc đoạn ~[R_2, R_1]~ sẽ bị tác động, đồng thời giá trị tài sản ở ô đó sẽ giảm đi min(w, b[i][j]), với ~b_{i,j}~ là giá trị tài sản hiện có ở ô ~(i, j)~.

Là một nước giáp biển, hằng năm đất nước Mirinda phải đón ~k~ trận bão. Do đặc trưng địa hình, bão sẽ chỉ đổ bộ vào một trong ~q~ ~(q < 5)~ điểm phân biệt. Rút kinh nghiệm từ siêu bão Fanta, ủy ban chống bão muốn biết sau khi ~k~ trận bão đó tàn phá thì nước này phải chịu tổng thiệt hại là bao nhiêu?

(Tổng thiệt hại của nước này được tính bằng tổng mức giảm giá trị tài sản của tất cả các ô).

Input

• Dòng đầu tiên chứa ~4~ số nguyên dương ~n,m,q,k~ (~1 < n, m < 500, k \leq 10^5~).
• ~n~ dòng tiếp theo, mỗi dòng chứa ~m~ số nguyên ~a_{i,j}~ (~0 < a_{i,j} < 10^9~).
• Dòng tiếp theo ghi ~2 \times q~ số nguyên là tọa độ của ~q~ điểm đặc biệt: ~x_1, y_1, x_2, y_2, \ldots, x_q, y_q~.
• ~k~ dòng cuối, mỗi dòng ghi ~5~ số nguyên mô tả cơn bão: ~w, R_1, R_2, x, y~ (~0 < R_2 < R_1 < 1000, 0 < w < 1000~). Dữ liệu đảm bảo ~x,y~ là ~1~ trong ~q~ điểm đã cho.

(Các trận bão sẽ được liệt kê theo đúng thứ tự đổ bộ).

Output

In ra tổng thiệt hại sau ~k~ cơn bão.

Sample Test

Input:

3 4 2 4
10 11 12 15
20 10 11 25
30 32 35 40
1 1 3 4
2 2 0 3 4
2 2 0 1 1
2 4 2 1 1
2 3 1 3 4

Output:

56

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

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