Yakumo Ran rất thích làm toán, hôm nay cô nghiên cứu bài toán sau:

Cho một mảng ~a~ có ~n~ phần tử, cho ~q~ truy vấn dạng l r x, hãy đếm số lượng số có giá trị ~x~ trong đoạn ~a[l...r]~.

Hiện tại cô chưa có lời giải cho bài toán này nên nhờ các bạn giúp!

Input

• Dòng đầu tiên gồm hai số tự nhiên ~n, q \le 10^5~.
• Dòng tiếp theo là mảng ~a~ nguyên với ~1 \le a_i \le 10^9~.
• ~q~ dòng tiếp theo mỗi dòng gồm 3 số ~l_i, r_i, x_i~ là truy vấn thứ ~i~.

Output

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

Sample Test

Input:

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

Output:

2
1

Cho ~N~ đoạn gỗ, để xử lí chúng, ta cần:

• Thời gian xử lí đoạn gỗ đầu tiên là 1 phút.
• Sau khi xử lí xong đoạn gỗ có chiều dài ~l~ và trọng lượng ~w~, không mất thời gian xử lí nếu đoạn gỗ tiếp theo có chiều dài ~l'~ và trọng lượng ~w'~ thỏa mãn ~l \le l'~ và ~w \le w'~, ngược lại mất 1 phút để xử lí.

Tìm thời gian chuẩn bị ít nhất cho ~N~ đoạn gỗ.

Ví dụ có 5 đoạn: ~(9,4), (2,5), (1,2), (5,3), (4,1)~ thì thời gian ít nhất là 2 vì có thể xử lí theo thứ tự sau: ~(4,1), (5,3), (9,4), (1,2), (2,5)~.

Input

Dòng đầu là số lượng test ~T \le 100~, mỗi test gồm:

• Dòng đầu là số nguyên dương ~N \le 5000~.
• Sau đó ~N~ dòng tiếp theo gồm ~N~ cặp số nguyên dương ~(l_1,w_1), (l_2,w_2), ..., (l_N,w_N)~, ~l_i,w_i <= 10000~ là độ dài và trọng lượng khối gỗ.

Output

In ra T dòng, mỗi dòng là đáp án của test tương ứng.

Sample Test

Input:

3

5 
4 9 
5 2 
2 1 
3 5 
1 4

3 
2 2 
1 1 
2 2

3 
1 3 
2 2 
3 1

Output:

2
1
3

Cho một dãy ~a~ gồm ~n~ phần tử. Ta định nghĩa ~g(l,r) = min (a[i]) \forall (l \le i \le r)~.

Tiếp đó, ta có ~f(k) = max (g(l,r)) \forall (r - l + 1= k)~, hay ~f(k)~ là giá trị lớn nhất của các ~g(l,r)~ với mọi đoạn ~(l,r)~ có độ dài ~k~.

Hãy lập trình tính các ~f(k)~ từ ~1 -> n~.

Input

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

Output

• In ra một dòng gồm ~n~ số miêu tả kết quả của ~f(k)~ từ ~1 -> n~.

Sample Test

Input:

10
1 2 3 4 5 4 3 2 1 6

Output:

6 4 4 3 3 2 2 1 1 1 

Sau khi bị Kanako cho ăn đập vì hệ thống cáp treo 1 chiều thì Kawashiro tiếp tục phải xây một hệ thống khác. Từ Nhân thôn đến Đền Moriya có ~n~ đỉnh núi cạnh nhau. Kawashiro cần chọn ra nhiều nhất số lượng số đỉnh núi sao cho độ cao của nó tăng chặt. Hỏi có bao nhiêu cách để cô có thể hoàn thành công việc?

Input

• Dòng đầu tiên gồm số tự nhiên ~n \le 10^5~.
• Dòng tiếp theo gồm ~n~ số tự nhiên ~a_i \le 10^9~ là độ cao của các đỉnh núi.

Output

• Số lượng cách chọn các đỉnh núi module ~10^9+7~

Sample Test

Input:

6
1 1 2 2 3 3

Output:

8

Có ~n~ địa điểm bên trong Rừng tre lạc lối được kết nối bằng ~m~ con đường một chiều. Một số con đường tạo thành một chu trình nên con người đi vào sẽ bị lạc. Fujiwara no Mokou muốn đổi hướng một số đường đi để không còn ai có thể bị lạc. Con đường thứ ~i~ có một chỉ số ~c_i~ có nghĩa là phải sử dụng sức mạnh tối thiểu ~c_i~ để đảo ngược nó.

Hãy cho biết cô cần sử dụng sức mạnh tối thiểu là bao nhiêu để không con chu trình trong rừng tre.

Input

• Dòng đầu tiên gồm 2 số ~n~ và ~m~.
• ~m~ dòng tiếp theo, dòng thứ ~i~ gồm 3 số ~u_i~, ~v_i~, ~c_i~ nghĩa là có đường một chiều từ ~u_i~ đến ~v_i~.

Output

• Dòng đầu 2 số lần lượt là in ra chỉ số sức mạnh nhỏ nhất phải sử dụng và số lượng ~k~ (không cần phải nhỏ nhất) là số lượng đường cần đảo ngược.
• Dòng tiếp theo in ra ~k~ chỉ số là các con đường cần phải đảo ngược.

Sample Test

Input:

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

Output:

2 2
1 3 

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~