Cho một dãy số gồm ~n~ phần tử ~a_1~, ~a_2~, ..., ~a_n~. Với một dãy số gồm ~m~ phần tử ~b_1~, ~b_2~, ..., ~b_m~, trọng số của dãy ~b~ được định nghĩa là tích của giá trị lớn nhất và nhỏ nhất của dãy. Hãy tìm tổng trọng số của các dãy con của dãy ~a~.

Dãy con của dãy ~a~ được định nghĩa là một tập ~a_{i_1}~, ~a_{i_2}~, ..., ~a_{i_k}~ với 1 ~\le~ ~i_1~ < ~i_2~ < ... < ~i_k~ ~\le~ ~n~.

INPUT

• Dòng đầu chứa số nguyên dương ~n~ (~1~ ~\le~ ~n~ ~\le~ ~10^5~).
• Dòng thứ hai chứ ~n~ số nguyên không âm ~a_i~ (~0~ ~\le~ ~a_i~ ~\le~ ~10^9~).

OUTPUT

• In ra một số nguyên duy nhất là tổng trọng số của tất cả các dãy con. Do output có thể rất lớn nên hãy in ra kết quả mod ~10^9 + 7~.

SAMPLE TEST

Input:

5
4 2 1 3 4

Output:

208

SUBTASKS

• ~30\%~ số điểm có ~n~ ~\le~ ~20~.
• ~30\%~ số điểm có ~n~ ~\le~ ~10^3~.
• ~40\%~ số điểm còn lại có ~n~ ~\le~ ~10^5~.

Trong dịp lễ giáng sinh, siêu thị ~ABC~ có chính sách giảm giá ~n~ mặt hàng. Các mặt hàng được trưng bày theo thứ tự từ trái qua phải với mức giá ưu đãi là ~p_i~, với số lượng không giới hạn với mỗi loại mặt hàng. Có ~m~ khách hàng thân thiết vô cùng yêu thích chương trình giảm giá này, người thứ ~i~ mang tới số tiền là ~t_i~ và sẽ đi từ vị trí ~l_i~ tới vị trí ~r_i~. Tại mỗi vị trí, người này sẽ cố gắng mua nhiều nhất số hàng có thể tới khi không còn đủ tiền mua.

Yêu cầu: Hãy xác định số tiền còn lại của từng người sau khi mua hàng.

Input

• Dòng đầu tiên chứa số nguyên dương ~n, m~
• Dòng thứ hai chứa ~n~ số, số thứ ~i~ là ~p_i~ mô tả giá tiền của mặt hàng thứ ~i~
• ~m~ dòng tiếp theo, dòng thứ ~i~ chứa ~3~ số nguyên ~t_i,l_i,r_i~ xác định số tiền và khoảng cách di chuyển của người thứ ~i~.

Constraints

• ~1 \le n,m \le 2*10^5~
• ~1 \le p_i,t_i \le 10^{18}~

Subtask

• Subtask ~1~ ~(50\%)~: ~1 \le n,m \le 5000; 1 \le p_i, t_i \le 10^9~
• Subtask ~2~ ~(50\%)~: Không có ràng buộc gì thêm

Sample Input 1

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

Sample Output 1

2
0
1

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

Có ~q~ truy vấn, mỗi truy vấn có dạng ~[l,r,x]~, yêu cầu hãy đếm xem có bao nhiêu ~a_i~ với ~i \in [l,r]~ thỏa mãn ~a_i~ là ước hoặc bội của ~x~.

Input

• Dòng đầu tiên gồm hai số nguyên dương ~n,q~.
• Dòng thứ hai gồm ~n~ số nguyên dương miêu tả dãy ~a~.
• ~q~ dòng sau, mỗi dòng gồm ~3~ số nguyên dương ~l,r,x~

Constraints

• ~1 \le n,q \le 2\times10^5~
• ~1 \le a_i, x \le 2\times10^5~

Output

• Với mỗi truy vấn, in ra kết quả.

Sample Input 1:

8 5
12 10 3 18 6 72 28 42
1 8 6
3 7 7
2 6 9
1 5 5
4 8 4

Sample Output 1:

6 1 3 1 2 

Bạn được cho hai mảng có độ dài ~n~ .

• Phần tử thứ ~i~ của mảng thứ nhất là ~a_i~ .
• Phần tử thứ ~i~ của mảng thứ hai là ~b_i~ .

Một cách chia cả hai mảng thành các mảng con không rỗng được gọi là tốt nếu thỏa mãn các điều kiện sau:

• Mỗi phần tử thuộc đúng một mảng con duy nhất.
• Số lượng mảng con của cả hai mảng bằng nhau, tức là nếu mảng thứ nhất được chia thành đúng ~k~ mảng con, thì mảng thứ hai cũng phải được chia thành đúng ~k~ mảng con.
• Với mọi ~1 \leq i \leq k~, trung bình cộng của mảng con thứ ~i~ bên trái mảng thứ nhất phải nhỏ hơn hoặc bằng trung bình cộng của mảng con thứ ~i~ bên trái mảng thứ hai.

Yêu cầu: Tính số cách để chia cả hai mảng thành các mảng con không rỗng thỏa mãn các điều kiện trên. Kết quả phải được chia dư với ~10^9 + 7~. Hai cách được xem là khác nhau nếu số lượng mảng con khác nhau hoặc nếu một phần tử thuộc về mảng con khác nhau.

Dữ liệu vào từ tệp văn bản: TRUNGBINHCONG.INP

• Dòng đầu tiên chứa số nguyên ~n~ ~(1 \leq n \leq 500)~.
• Dòng tiếp theo chứa ~n~ số nguyên ~a_1, a_2, \dots, a_n~ ~(1 \leq a_i \leq 10^6)~.
• DDòng cuối cùng chứa ~N~ số nguyên ~b_1, b_2, \dots, b_n~ ~(1 \leq b_i \leq 10^6)~.

Kết quả ghi ra tệp văn bản: TRUNGBINHCONG.OUT

• In ra số cách chia mảng thỏa mãn các điều kiện, chia dư với ~10^9 + 7~.

Scoring

• Subtask ~1~ (~20\%~ số điểm): ~n \le 10~
• Subtask ~2~ (~30\%~ số điểm): ~n \le 80~
• Subtask ~3~ (~30\%~ số điểm): ~n \le 300~
• Subtask ~4~ (~20\%~ số điểm): Không giới hạn gì thêm.

Example

Sample Input 1

3
1 3 2
2 2 2

Sample Output 1

3

Note

Ba cách hợp lệ là:

• Chia mảng thứ nhất thành ~[1, 3], [2]~ và mảng thứ hai thành ~[2, 2], [2]~.
• Chia mảng thứ nhất thành ~[1, 3], [2]~ và mảng thứ hai thành ~[2], [2, 2]~.
• Chia mảng thứ nhất thành ~[1, 3, 2]~ và mảng thứ hai thành ~[2, 2, 2]~.

Cho hai dãy số nguyên ~a, b~ có cùng độ dài ~n~ và một số nguyên ~S~. Có ~Q~ truy vấn thuộc một trong hai dạng sau:

• ~1~ ~x~ ~y~: Gán ~a_i = x, b_i = y~
• ~2~ ~H~: Cần tìm ~1 \le L \le H~ sao cho ~a_L + a_{L+1} + ... + a_H \ge S~ và ~b_L + b_{L+1} + ... + b_H~ đạt giá trị nhỏ nhất có thể.

Input

• Dòng đầu tiên chứa hai số nguyên ~n, S~ ~(1 ≤ n ≤ 10^5, -10^{18} ≤ S ≤ 10^{18})~.
• Dòng thứ hai chứa ~n~ số nguyên ~a_1, a_2, . . . , a_n (-10^9 ≤ a_i ≤ 10^9)~
• Dòng thứ ba chứa ~n~ số nguyên ~b_1, b_2, . . . , b_n~ ~(-10^9 ≤ b_i ≤ 10^9)~
• Dòng thứ tư chứa số nguyên dương ~Q~ ~(1 ≤ Q ≤ 10^5)~
• ~Q~ dòng tiếp theo, mỗi dòng ghi một truy vấn: ~1~ ~i~ ~x~ ~y~ ~(1 ≤ i ≤ n; -10^9 ≤ x, y ≤ 10^9)~ hoặc ~2~ ~H~ ~(1 ≤ H ≤ n)~

Output

• Với mỗi truy vấn, in ra trên một dòng là giá trị nhỏ nhất có thể của ~b_L + b_{L+1} + . . . + b_H~ hoặc ~-1~ nếu không tồn tại ~L~ thoả mãn.

Subtask

• Subtask ~1~ ~(25\%)~: ~a_i = 1~ tại mọi thời điểm.
• Subtask ~2~ ~(25\%)~: ~b_i = 1~ tại mọi thời điểm.
• Subtask ~3~ ~(25\%)~: Chỉ tồn tại các truy vấn loại ~2~.
• Subtask ~4~ ~(25\%)~: Không có ràng buộc nào thêm.

Sample Input 1

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

Sample Output 1

4
3