Trên mặt phẳng toạ độ người ta vẽ ra ~n~ hình chữ nhật.

Hãy tính diện tích bị che phủ bởi ~n~ hình chữ nhật này, biết rằng ~n~ hình chữ nhật đó đều song song với trục ~OX~ và ~OY~.

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 \le 10^5~
• ~1 \le x_i, y_i \le 3\times10^4~

Output

• Gồm một dòng in ra diện tích được phủ bởi ~n~ hình chữ nhật.

Sample Input 1:

2
10 10 20 20
15 15 25 30

Sample Output 1:

225

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

Xét một xâu có chiều dài ~n~ bao gồm các chữ số ~0~ hoặc ~1~. Điểm của xâu được tính như sau:

• Với mỗi số nguyên ~i~ ~(1 \le i \le m)~, tổng điểm của xâu sẽ được tăng thêm ~a_i~ nếu như xâu con bao gồm các kí tự từ ~l_i~ đến ~r_i~ (kể cả biên) có ít nhất một kí tự ~1~.

Với mọi xâu độ dài ~n~, số điểm cao nhất có thể đạt được là bao nhiêu.

Input

• Dòng đầu tiên gồm hai số nguyên ~n,m~
• ~m~ dòng tiếp theo, dòng thứ ~i~ chứa ba số nguyên ~l_i,r_i,a_i~.

Constraints

• ~1 \le n,m \le 2*10^5~
• ~1 \le l_i,r_i \le n, |a_i| \le 10^9~

Subtask :

• Subtask 1: ~n \le 5000~ ~(50\%)~
• Subtask 2: ~n \le 5*10^5~ ~(50\%)~

Output

• In ra số điểm lớn nhất có thể.

Sample Input 1:

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

Sample Output 1:

20

Explanation 2:

• Xâu 10001 là xâu tối ưu.

Sample Input 2:

3 4
1 3 100
1 1 -10
2 2 -20
3 3 -30

Sample Output 2:

90

Explanation 2:

• Xâu 100 là xâu tối ưu.

Sample Input 3:

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

Sample Output 3:

10

Explanation 3:

• Xâu 101000 là xâu tối ưu.

Là sinh viên ngành Công nghệ thông tin, Nam thường xuyên rèn luyện tư duy và kĩ năng lập trình bằng các bài toán lập trình thi đấu. Một bài toán thú vị mà Nam đang suy nghĩ để giải như sau:

Cho ~n~ đoạn số nguyên trên trục số, đoạn thứ ~k~ ~(1 \le k \le n)~ có đầu mút bên trái là ~L_k~, đầu mút bên phải là ~R_k~ và có trọng số là ~w_k~. Với ~a,b~ là hai số nguyên, trọng số của ~(a,b)~ được tính bằng tổng trọng số của tất cả các đoạn ~t~ mà ~a \le L_t \le R_t \le b~ với ~1 \le t \le n~. Cần tìm số nguyên ~(a,b)~ có trọng số lớn nhất.

Yêu Cầu: Cho ~n~ đoạn số, gọi ~S~ là trọng số của cặp số nguyên ~(a,b)~ có trọng số là lớn nhất, hãy giúp Nam xác định giá trị ~S~.

Input

• Dòng đầu tiên gồm hai số nguyên dương ~n~.
• Dòng thứ ~k~ ~(1 \le k \le n)~ trong ~n~ dòng tiếp theo chứa ba số nguyên ~L_k,R_k,w_k~ mô tả đoạn thứ ~k~ ~(1 \le L_k \le R_k \le 10^6; |w_k| \le 10^6)~

Subtask

• Có ~30\%~ số test có: ~n \le 200~.
• Có ~30\%~ số test có: ~n \le 2000~.
• Có ~20\%~ số test có: ~R_1 - L_1 = R_2 - L_2 = ... = R_n - L_n~ và ~n \le 10^5~.
• Có ~20\%~ số test có: ~n \le 10^5~.

Output

• Gồm một số nguyên ~S~ là trọng số lớn nhất tìm được.

Sample Input 1:

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

Sample Output 1:

8

Explanation 1:

Trọng số lớn nhất là ~8~ bằng cách chọn cặp số ~(3,6)~.

Trọng số của cặp số ~(3,6)~ bằng tổng trọng số của ba đoạn: ~[3,5],[3,4]~ và ~[4,6]~.

Ta định nghĩa hàm ~phi(n)~ là số lượng số nguyên dương bé hơn hoặc bằng ~n~ và nguyên tố cùng nhau với ~n~. Ta coi ~phi(1) = 1~.

Cho ~q~ truy vấn, mỗi truy vấn gồm một số nguyên dương ~n~, hãy in ra ~phi(n)~.

Input

• Dòng đầu gồm số nguyên dương ~q \le 100000~.
• ~Q~ dòng sau, mỗi dòng gồm một số ~n \le 1000000~ miêu tả ~q~ truy vấn.

Output

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

Sample Test

Input:

5
15
17
14
18
17

Output:

8
16
6
6
16

Ta định nghĩa hàm ~phi(n)~ là số lượng số nguyên dương bé hơn hoặc bằng ~n~ và nguyên tố cùng nhau với ~n~. Ta coi ~phi(1) = 1~.

Thầy Gojo Satoru có một mảng ~a~ nguyên dương gồm ~n~ phần tử.

Để tạo ra một bài toán hóc búa, thầy có ~m~ truy vấn như sau:

• Truy vấn thứ ~i~ gồm các số ~(l_i,r_i)~, gọi ~f(l,r)~ là tích của tất cả ~a_i \forall (l \le i \le r)~, hãy tính ~phi(f(l_i,r_i))~.
• Vì kết quả có thể rất lớn nên hãy in ra phần dư của nó khi mod ~10^9+7~.

Hãy lập trình tính toán kết quả cho mỗi truy vấn.

Input

• Dòng đầu gồm số nguyên dương ~n~. (~n \le 200000~)
• Dòng sau gồm ~n~ số nguyên dương miêu tả dãy ~a~. (~a_i \le 200000~)
• Dòng tiếp theo là số nguyên dương ~m \le 200000~ miêu tả số truy vấn.
• ~M~ dòng tiếp theo, mỗi dòng gồm 2 số nguyên dương ~l_i, r_i~ ~(1 \le l_i \le r_i \le n)~, miêu tả các truy vấn.

Output

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

Sample Test

Input:

7
24 63 13 52 6 10 1
6
3 5
4 7
1 7
2 4
3 6
2 6

Output:

1248
768
12939264
11232
9984
539136

Giải thích

Ta có:

• ~phi(13*52*6) = phi(4056) = 1248~
• ~phi(52*6*10*1) = phi(3120) = 768~
• ~phi(24*63*13*52*6*10*1) = phi(61326720) = 12939264~
• ~phi(63*13*52) = phi(42588) = 11232~
• ~phi(13*52*6*10) = phi(40560) = 9984~
• ~phi(63*13*52*6*10) = phi(2555280) = 539136~