Cho một dãy số nguyên ~A~ gồm ~N~ phần tử ~A_1, A_2, \ldots, A_N~.

Một đoạn con liên tiếp của dãy là một đoạn có dạng:

• ~A_x, A_{x+1}, \ldots, A_y~, với ~1 \le x \le y \le N~.

Có ~Q~ truy vấn. Mỗi truy vấn gồm hai số nguyên ~l, r~. Với mỗi truy vấn, hãy tìm tổng lớn nhất của một đoạn con liên tiếp không rỗng nằm hoàn toàn trong đoạn ~A_l, A_{l+1}, \ldots, A_r~.

Nói cách khác, với mỗi truy vấn ~l, r~, cần tính:

• ~\max_{l \le x \le y \le r}(A_x + A_{x+1} + \ldots + A_y)~

Input

• Dòng đầu tiên chứa hai số nguyên ~N~ và ~Q~.
• Dòng thứ hai chứa ~N~ số nguyên ~A_1, A_2, \ldots, A_N~.
• ~Q~ dòng tiếp theo, mỗi dòng chứa hai số nguyên ~l~ và ~r~ mô tả một truy vấn.

Output

• Với mỗi truy vấn, in ra một dòng là tổng đoạn con liên tiếp lớn nhất nằm hoàn toàn trong đoạn được hỏi.

Ràng buộc

• ~1 \le N, Q \le 5 \cdot 10^5~
• ~-10^9 \le A_i \le 10^9~
• ~1 \le l \le r \le N~

Subtask

Sample Input 1

8 4
1 -2 3 4 -1 2 -5 6
1 8
3 6
2 5
7 8

Sample Output 1

8
8
7
6

Giải thích

• Với truy vấn ~[1, 8]~, đoạn tốt nhất là ~[3, 4, -1, 2]~ có tổng ~8~.
• Với truy vấn ~[3, 6]~, toàn bộ đoạn ~[3, 4, -1, 2]~ có tổng ~8~.
• Với truy vấn ~[2, 5]~, đoạn tốt nhất là ~[3, 4]~ có tổng ~7~.
• Với truy vấn ~[7, 8]~, đoạn tốt nhất là ~[6]~ có tổng ~6~.

Sample Input 2

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

Sample Output 2

-1
-1
-7

Giải thích

Đoạn con phải không rỗng. Vì tất cả phần tử đều âm, đáp án của mỗi truy vấn là phần tử lớn nhất trong đoạn được hỏi.

Có ~n~ đồ vật được đánh số từ ~1~ tới ~n~. Đồ vật thứ ~i~ có trọng lượng là ~w_i~ và có giá trị là ~v_i~.

Bạn cần trả lời ~q~ truy vấn, truy vấn thứ ~i~ gồm ba số nguyên ~l_i~, ~r_i~ , ~W_i~, hỏi rằng giả sử nếu chỉ xét các đồ vật trong đoạn ~[l_i,r_i]~, thì với tổng trọng lượng tối đa là ~W_i~, bạn có thể thu được tổng giá trị lớn nhất là bao nhiêu? Biết rằng mỗi đồ vật trong đoạn đó bạn chỉ có thể lấy tối đa một lần.

Input

• Dòng đầu gồm số nguyên dương ~n~ ~(1 \le n \le 10^4)~
• ~n~ dòng sau, dòng thứ ~i~ gồm hai số nguyên dương miêu tả đồ vật thứ ~i~: ~w_i~ và ~c_i~ ~(1 \le w_i \le 100, c_i \le 10^4)~.
• Dòng tiếp theo gồm số nguyên dương ~q~ miêu tả số truy vấn ~(q \le 10^5)~.
• ~q~ dòng sau, dòng thứ ~i~ gồm ba số nguyên dương miêu tả truy vấn thứ ~i~: ~l_i~, ~r_i~, ~W_i~ ~(1 \le l_i \le r_i \le n; 1 \le W_i \le 100)~.

Output

• Gồm ~q~ dòng, dòng thứ ~i~ là kết quả của truy vấn thứ ~i~.

Subtask

• Subtask ~1~: ~r-l \le 100~ ~(40\%)~
• Subtask ~2~: ~q \le 10^4~ ~(30\%)~
• Subtask ~3~: Không giới hạn gì thêm ~(30\%)~

Example

Sample Input 1

4
2 15
2 20
4 36
1 4
3
1 2 4
1 4 7
3 4 2

Sample Output 1

35
60
4

Cho mảng ~A~ gồm ~n~ phần tử nguyên. Định nghĩa hàm ~f(l, r)~ là:

• ~max(A_{l...r}) \times min(A_{l...r})~

Tính:

• ~\sum_{l=1}^{n} \sum_{r=l}^{n} f(l, r)~

Input

• Dòng đầu tiên gồm số nguyên ~n~.
• Dòng thứ hai gồm ~n~ số nguyên ~A_i~.

Output

• In ra kết quả, modulo ~10^9+7~.

Điều kiện

• ~1 \le n \le 10^5~.
• ~1 \le A_i \le 10^9~.

Ví dụ

Input:

4
1 4 3 1

Output:

58

Cho bảng số ~A~ kích thước ~n*m~, các hàng được đánh số từ trên xuống dưới, các cột được đánh số từ trái sang phải. Ô giao giữa hàng ~i~ cột ~j~ là ô ~(i,j)~ và có giá trị ~a(i,j)~. Hai ô có thể di chuyển tới nhau nếu chúng chung cạnh. Một đường đi sẽ bao gồm các ô sao cho hai ô liên tiếp chung cạnh, và nó có giá trị bằng tổng giá trị các ô trên đường đi.

Cho ~q~ truy vấn, truy vấn thứ ~i~ sẽ cho bạn hai ô ~(x,y)~ và ~(u,v)~ trong bảng. Kết quả của một truy vấn chính là giá trị của đường đi có trọng số nhỏ nhất giữa hai ô đã cho. Hãy in ra kết quả của từng truy vấn.

Input

• Dòng đầu tiên chứa hai số nguyên dương ~n,m~, ~(1 \le n \le 7; 1 \le m \le 5000)~.
• Tiếp theo là ~n~ dòng, mỗi dòng gồm ~m~ số nguyên không âm miêu tả bảng ~A~ ~n*m~, ~(0 \le a(i,j) \le 10^5)~ .
• Dòng tiếp theo là số nguyên dương ~q~, ~(q \le 30000)~.
• Ở ~q~ dòng tiếp theo mỗi dòng miêu tả một truy vấn, truy vấn thứ ~i~ có dạng ~x_i, y_i, u_i, v_i~ miêu tả ô ~(x_i,y_i)~ và ~(u_i,v_i)~. (Các ô đều nằm trong bảng).

Output

• In ra ~q~ dòng là kết quả của ~q~ truy vấn.

Sample Test

Input:

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

Output:

5
9

Xe buýt là một phương tiện giao thông phổ biến tại thành phố mà Alice sinh sống bởi tính tiện dụng và giá cả hợp lý của nó. Thành phố có ~n~ bến xe buýt được đánh số từ ~1~ tới ~n~ và có ~m~ tuyến xe buýt hai chiều, mỗi tuyến đang được điều hành bởi một trong hai công ty vận tải ~A~ hoặc ~B~. Cụ thể, tuyến thứ ~i~ ~(1 \le i \le m)~ di chuyển giữa hai bến ui và vi với giá vé do công ty quản lý quy định là ~w_i~.

Lưu ý là giữa hai bến có thể có nhiều hơn một tuyến xe buýt. Hai công ty ~A~ và ~B~ đều có chính sách giảm giá vé cho những ai thường xuyên đi bằng xe buýt. Cụ thể, mỗi ngày công ty ~A~ sẽ chỉ thu số tiền bằng với giá vé lớn nhất trong tất cả các tuyến được điều hành bởi công ty ~A~ mà khách hàng đã đi trong ngày. Để cạnh tranh, công ty ~B~ cũng có chính sách tương tự: khách hàng sẽ chỉ phải trả số tiền bằng giá vé lớn nhất trong tất cả các tuyến thuộc công ty ~B~ mà người đó đã đi trong ngày.

Nhà Alice ở gần bến xe buýt ~s~ và nơi làm của Alice ở gần bến xe buýt ~t~ nên hàng ngày Alice đều phải đi lại giữa hai bến này thông qua các tuyến xe buýt.

Yêu cầu: Bạn hãy giúp Alice xác định số tiền nhỏ nhất cần bỏ ra mỗi ngày để đảm bảo việc đi từ bến xe buýt ~s~ đến bến xe buýt ~t~.

Input:

• Dòng đầu tiên chứa bốn số nguyên dương ~n, m, s~ và ~t~ ~(n, m \le 50000; s, t \le n; s \neq t)~;
• Dòng thứ ~i (1 \le i \le m)~ trong ~m~ dòng tiếp theo chứa bốn số nguyên dương ~c_i, u_i, v_i, w_i~ ~(u_i, v_i \le n; u_i \neq v_i; w_i \le 10^9)~ mô tả tuyến xe buýt thứ i trong đó ~c_i = 1~ nếu tuyến này được điều hành bởi công ty ~A~ hoặc ~c_i = 2~ nếu tuyến này được điều hành bởi công ty ~B~.

Các số trên cùng một dòng cách nhau bởi dấu cách. Dữ liệu đảm bảo luôn tồn tại cách đi lại giữa hai bến xe buýt ~s~ và ~t~ thông qua ~m~ tuyến xe.

Output:

• In ra một số nguyên duy nhất là số tiền nhỏ nhất cần bỏ ra mỗi ngày để đảm bảo được việc đi từ bến xe buýt ~s~ đến bến xe buýt ~t~ cho Alice.

Subtask

• Subtask ~1~ ~(30\%)~: tất cả xe buýt đều được điều hành bởi công ty ~A~.
• Subtask ~2~ ~(30\%)~: ~n,m \le 5000~
• Subtask ~3~ ~(40\%)~: không ràng buộc gì thêm.

Sample Input 1

6 7 1 4
1 1 2 4
2 2 3 7
1 3 4 6
2 1 6 5
1 6 5 5
2 5 4 8
2 2 5 2

Sample Output 1

12

Explanation 1

Để đi từ ~1~ tới ~4~, Alice đi tuyến ~(1,2)~ của công ty ~A~ và hai tuyến ~(2,5)~ và ~(5,4)~ của công ty ~B~. Khi đó Alice cần trả cho công ty ~A~ ~4~ và công ty ~B~ ~8~ đơn vị tiền.

Trong giờ số học, cô giáo đưa ra dãy ~A~ gồm ~N~ số nguyên dương từ ~1~ đến ~N~.

Cô cho mỗi học sinh chọn một dãy con ~B~ gồm các phần tử liên tiếp của ~A~. Dãy con ~B~ được gọi là dãy đẹp nếu khi sắp xếp ~B~ theo thứ tự tăng dần, ta thu được một dãy số nguyên liên tiếp.

Dãy con chỉ gồm một phần tử cũng được gọi là dãy đẹp.

Ví dụ, ~B = [2, 4, 3]~ là dãy đẹp, trong khi ~B = [2, 3, 2]~ không phải là dãy đẹp.

Yêu cầu

Hãy đếm số lượng dãy con đẹp của ~A~.

Input

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

Output

• In ra một số nguyên duy nhất là số lượng dãy con đẹp của ~A~.

Scoring

Sample Input

3
1 2 3

Sample Output

6

Giải thích ví dụ

Có ~6~ dãy con đẹp là:

~[1]~, ~[2]~, ~[3]~, ~[1, 2]~, ~[2, 3]~, ~[1, 2, 3]~

Cho một lưới ô vuông gồm ~m~ hàng và ~n~ cột. Các hàng được đánh số từ ~1~ đến ~m~, các cột được đánh số từ ~1~ đến ~n~.

Ban đầu, mỗi ô trong lưới đều chứa giá trị ~0~.

Có ~q~ truy vấn, mỗi truy vấn thuộc một trong hai loại sau:

• ~1~ ~i~ ~j~ ~v~: Tăng giá trị tại ô ~(i, j)~ thêm ~v~ đơn vị.
• ~2~ ~x_1~ ~y_1~ ~x_2~ ~y_2~: Tính tổng các giá trị trong hình chữ nhật con có góc trên trái ~(x_1, y_1)~ và góc dưới phải ~(x_2, y_2)~.

Input

• Dòng đầu tiên chứa ba số nguyên dương ~m, n, q~ ~(m, n \le 10^9, q \le 10^5)~.
• ~q~ dòng tiếp theo, mỗi dòng mô tả một truy vấn thuộc một trong hai dạng:
  • ~1~ ~i~ ~j~ ~v~ ~(1 \le i \le m, 1 \le j \le n, |v| \le 10^9)~
  • ~2~ ~x_1~ ~y_1~ ~x_2~ ~y_2~ ~(1 \le x_1 \le x_2 \le m, 1 \le y_1 \le y_2 \le n)~

Output

• Với mỗi truy vấn loại ~2~, in ra kết quả của truy vấn đó trên một dòng riêng.

Sample Input

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

Sample Output

1
6
3
0

Giải thích ví dụ

Sau truy vấn ~1~, ô ~(2, 3)~ có giá trị ~1~.

• Truy vấn ~2~ hỏi tổng hình chữ nhật từ ~(1, 1)~ đến ~(2, 3)~, chứa ô ~(2, 3)~, nên kết quả là ~1~.
• Sau đó ô ~(2, 3)~ được tăng thêm ~2~, nên giá trị ô này thành ~3~.
• Ô ~(3, 1)~ được tăng thêm ~3~.
• Truy vấn tiếp theo hỏi toàn bộ lưới, tổng là ~3 + 3 = 6~.
• Truy vấn tiếp theo hỏi ô ~(3, 1)~, kết quả là ~3~.
• Truy vấn cuối hỏi các ô từ ~(3, 2)~ đến ~(3, 3)~, không có ô nào khác ~0~, nên kết quả là ~0~.

Subtask

Cho đồ thị vô hướng gồm ~n~ đỉnh và ~m~ cạnh. Các cạnh được đánh số từ ~1~ tới ~m~, cạnh thứ ~i~ nối hai đỉnh ~u_i~ và ~v_i~.

Bạn cần xử lí ~q~ truy vấn, truy vấn thứ ~i~ có dạng sau:

• Cho hai số ~L_i~ và ~R_i~, giả sử chúng ta xóa hết các cạnh được đánh số trong khoảng ~[L_i,R_i]~, hỏi rằng liệu đồ thị mới có tồn tại ít nhất một chu trình lẻ hay không.
• Lưu ý rằng đây chỉ là giả định, các truy vấn ta chỉ xét với đồ thị gốc.

Input

• Dòng đầu gồm ba số nguyên ~n,m,q~.
• ~m~ dòng tiếp theo, dòng thứ ~i~ gồm hai số nguyên ~u_i,v_i~ miêu tả cạnh thứ ~i~.
• ~q~ dòng sau, dòng thứ ~i~ gồm hai số nguyên dương ~L_i~, ~R_i~ miêu tả truy vấn thứ ~i~.

Output

• Với mỗi truy vấn, in ra "0" nếu như không tồn tại chu trình lẻ, ngược lại in ra "1".

Constraints

• ~1 \le n,m,q \le 2 \times 10^5~.
• ~1 \le u_i \neq v_i \le n~.
• ~1 \le L_i \le R_i \le n~

Subtask

• ~20\%~ số điểm có ~n,m,q \le 2000~.
• ~30\%~ số điểm có ~L_i = 1 \forall i \in [1,q]~.
• ~30\%~ số điểm có ~Q \le 2000~
• ~20\%~ số điểm còn lại không có ràng buộc gì thêm.

Sample Input 1

7 9 4
1 3
1 4
2 5
3 6
4 6
1 6
3 2
5 7
2 7

1 2
3 5
4 7
8 9

Sample Output 1

1
0
1
1