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

Người thầy quốc dân Gojo Satoru giờ đang có một niềm đam mê với tin học. Để lan tỏa điều này, anh muốn đố các học sinh của mình một bài toán như sau: Cho một dãy số nguyên ~a~ gồm ~n~ phần tử, định nghĩa ~f(l,r)~ là ~max(a_i) - min(a_i) \forall (l \le i \le r)~.

Hãy tính tổng của ~f(l,r) \forall (1 \le l \le r \le n)~.

Tất nhiên, do bận đi làm nhiệm vụ, các học sinh của thầy không rảnh để giải bài toán này, hãy thử giải nó giúp họ nhé.

Input:

• Dòng đầu gồm số nguyên dương ~n~. ~(1 \le n \le 10^5)~.
• Dòng sau gồm n số nguyên miêu tả dãy ~a~. ~(|a_i| \le 10^6)~.

Output:

• Ghi ra một số nguyên miêu tả kết quả của bài toán.

Subtasks

• Subtask 1: ~n \leq 5000~. (50%)
• Subtask 2: Không giới hạn gì thêm.

Sample Test

Input:

3
1 2 3

Output:

4

Giải thích:

Ta có ~f(1,1) + f(1,2) + f(1,3) + f(2,2) + f(2,3) + f(3,3) = 0 + 1 + 2 + 0 + 1 +0 = 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

Hệ thống giao thông của thành phố mà DN được quy hoạch có dạng một lưới hình chữ nhật gồm ~m \times n~ ô vuông đơn vị với các con đường ngang và dọc chạy xuôi theo các ô của lưới. Các con đường ngang bắt đầu từ bên trái sang bên phải của lưới, song song với nhau và được đánh số từ 1 đến ~m + 1~ theo thứ tự từ trên xuống dưới. Các con đường dọc bắt đầu từ phía trên xuống phía dưới của lưới, song song với nhau và được đánh số từ 1 đến ~n + 1~ theo thứ tự từ trái sang phải. Giao của đường ngang thứ ~u~ với đường dọc thứ ~v~ gọi là địa điểm ~(u, v)~.

Nơi ở hoặc nơi làm việc của người dân là một địa điểm trên lưới. Ban quy hoạch đô thị đã khảo sát được hằng ngày có một số lượng lớn người dân có thói quen ghé qua siêu thị sau giờ làm rồi mới về nhà. Căn cứ vào dữ liệu của ~d~ người dân có nơi ở là các địa điểm lần lượt tương ứng là ~A_1, A_2, ..., A_d~ và có nơi làm việc tương ứng là ~B_1, B_2, ..., B_d~ (người ở địa điểm ~A_i~ làm việc tại địa điểm ~B_i~, ~1 \leq i \leq d~). Bạn quy hoạch quyết định chọn một tuyến phố thương mại xuôi theo một con đường ngang để xây dựng một số lượng ~k~ siêu thị phục vụ người dân thuận tiện sinh hoạt, tiết kiệm chi phí và thời gian đi lại. Các siêu thị được đặt tại các địa điểm trên lưới và có thể trùng với địa điểm nơi ở hoặc nơi làm việc của người dân.

Yêu cầu: Hãy giúp ban quy hoạch chọn một con đường ngang và ~k~ địa điểm trên con đường ngang này để xây dựng các siêu thị sao cho tổng tất cả độ dài quãng đường từ nơi làm việc của từng người đến một siêu thị và từ siêu thị đó trở về nơi ở là nhỏ nhất. Độ dài quãng đường từ địa điểm ~(u, v)~ đến địa điểm ~(u', v')~ tính bằng ~|u - u'| + |v - v'|~.

Input

• Dòng đầu tiên chứa bốn số nguyên dương ~m, n, d, k~, với ~m, n \leq 10^9; k \leq 15~.
• Dòng thứ hai chứa ~d~ cặp số nguyên dương ~a_1, b_1, a_2, b_2, ..., a_d, b_d~ với ~1 \leq a_i \leq m + 1~ và ~1 \leq b_i \leq n + 1~ với mọi ~1 \leq i \leq d~ là địa điểm nơi ở của người dân.
• Dòng thứ ba chứa ~d~ cặp số nguyên dương ~x_1, y_1, x_2, y_2, ..., x_d, y_d~ với ~1 \leq x_i \leq m + 1~ và ~1 \leq y_i \leq n + 1~ với mọi ~1 \leq i \leq d~ là địa điểm nơi làm việc của người dân.

Output

• Ghi ra thiết bị ra chuẩn một số nguyên duy nhất là tổng độ dài quãng đường nhỏ nhất cần thiết khi đặt ~k~ siêu thị trên cùng một đường ngang.

Subtask

• Có ~15\%~ số test ứng với ~15\%~ số điểm của bài thỏa mãn ~d \leq 300~ và ~b_i = y_i~ (với mọi ~1 \leq i \leq d~);
• ~20\%~ số test tiếp theo ứng với ~20\%~ số điểm của bài thỏa mãn ~d \leq 3000~ và ~b_i = y_i~ (với mọi ~1 \leq i \leq d~);
• ~20\%~ số test khác ứng với ~20\%~ số điểm của bài thỏa mãn ~d \leq 300~;
• ~25\%~ số test khác ứng với ~20\%~ số điểm của bài thỏa mãn ~d\leq 3000~;
• ~20\%~ số test còn lại ứng với ~20\%~ số điểm của bài thỏa mãn ~d \leq 5 \times 10^4~.

Example

Input 1

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

Output 1

24

Explanation 1

Giải thích ví dụ: Bạn quy hoạch đô thị chọn con đường ngang số 3 và hai siêu thị ~S_1~, ~S_2~ ở vị trí giao với đường dọc số 3 và số 4. Lịch trình di chuyển hằng ngày từ nơi làm việc về nhà của bốn người dân như sau:

• Người thứ nhất đi từ ~B_1~ đến ~S_2~, rồi về ~A_1~, với tổng quãng đường là ~8~;
• Người thứ hai đi từ ~B_2~ đến ~S_2~, rồi về ~A_2~, với tổng quãng đường là ~4~;
• Người thứ ba đi từ ~B_3~ đến ~S_1~, rồi về ~A_3~, với tổng quãng đường là ~6~;
• Người thứ tư đi từ ~B_4~ đến ~S_1~, rồi về ~A_4~, với tổng quãng đường là ~6~.