Mùa tuyển sinh đã đến, là một người đã cố gắng suốt cả năm qua nên AP đang phải đau đầu để chọn trường cho mình. Ting ting tiếng chuông điện thoại của AP kêu lên và AP nhận được một tin nhắn từ Hogwarts báo nhập học, AP đồng ý ngay. Đời không như mơ, để bước vào ngôi trường pháp thuật trứ danh này AP phải qua một bài kiểm tra của thầy hiệu trưởng như sau:

AP được phù phép dịch chuyển đến một mỏm đá, trước mặt AP là những hòn đảo được đánh số từ ~1~ đến ~n~ có diện tích là ~w_i~, giữa những hòn đảo có ~m~ cây cầu được xây sắn bằng phép thuật, cây cầu thứ ~j~ nối hai đảo ~u_i~ và ~v_j~ lại với nhau. Thầy hiệu trưởng muốn qua bài thi này để đánh giá khả năng sử dụng thần chú của AP với đề bài là hai thần chú:

• ~C~ ~i~ ~W~ có tác dụng thay đổi kích thước của hòn đảo thứ ~i~ thành diện tích ~W~
• ~D~ ~j~ có tác dụng xóa đi cầy cầu thứ ~j~ (nếu lúc này nó vẫn tồn tại) nối hai hòn đảo ~u_i~ và ~v_j~.

Sau mỗi thao tác thay đổi như thế, thầy hiệu trưởng muốn biết tổng diện tích lớn nhất của những hòn đảo đến được với nhau. Vốn trí nhớ AP không được tốt và AP cũng khá lười để trả lời những câu hỏi của thầy khi thực hiện một đống phép thuật nên AP cần bạn hơn bao giờ hết. Hãy giúp AP trả lời câu hỏi của thầy hiệu trưởng để vượt qua bài kiểm tra nha.

Input:

• Dòng thứ nhất gồm ~3~ số nguyên ~n,m,q~ ~(n,m,q \le 3*10^5)~
• Dòng thứ hai cho biết diện tích ban đầu của ~n~ hòn đảo lần lượt là ~w_1,w_2,...,w_n~ ~(w_i \le 10^9)~
• ~m~ dòng tiếp theo cho biết thứ tự và thông tin các cây cầu được xây sẵn, cây cầu thứ ~j~ nối giữa hai hòn đảo là ~u_i~ và ~v_j~.
• ~q~ dòng tiếp theo cho biết thầy hiệu trưởng yêu cầu AP sử dụng thần chú ~C~ ~i~ ~W~ hoặc ~D~ ~j~.

Output

• ~q~ dòng được in ra là câu trả lời cho yêu cầu của thầy hiệu trưởng, vì thầy hiệu trưởng là một người thông thái cho nên khi đặt câu hỏi cho AP thì luôn có câu trả lời cho câu hỏi đó.

Subtask

• Có ~30\%~ số test chứa ~n,m,q \le 5000~.
• ~70\%~ số test còn lại không có ràng buộc gì thêm.

Sample Input 1

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

Sample Output 1

15
11
11
11
17
17
17
9

Cho cây ~n~ đỉnh gồm ~n-1~ cạnh có gốc tại đỉnh ~1~. Đỉnh thứ ~i~ có giá trị là ~a_i~.

Đối với mỗi đỉnh ~u~, ta cần phải tính độ đẹp của đường đi xuất phát từ gốc là đỉnh ~1~ tới ~u~. Độ đẹp trên đường đi này được tính như sau:

• Ta có thể chọn tối đa một đỉnh ~v~ bất kì thuộc đường đi từ ~1~ tới ~u~, sau đó gán giá trị ~a_v = 0~.
• Tiếp theo, tính giá trị ~X =~ ước chung lớn nhất theo giá trị của các đỉnh thuộc đường đi từ ~1~ tới ~u~.
• Độ đẹp của đường đi từ ~1~ tới ~u~ là cách thay đỉnh tốt nhất (hoặc có thể giữ nguyên giá trị các đỉnh) sao cho giá trị ~X~ thu được là lớn nhất.

Với mỗi ~u~ từ ~1~ tới ~n~, bạn cần tính được độ đẹp của đường đi ~(1,u)~, lưu ý các truy vấn ở đây là độc lập, nghĩa là bạn không thay đổi thực sự một giá trị nào cả.

Input

• Dòng đầu chứa số nguyên ~n~ ~( n \le 2 \times 10^5)~.
• Dòng tiếp theo gồm ~n~ số nguyên dương miêu tả dãy ~a~ ~(1 \le a_i \le 2 \times 10^5)~
• ~n-1~ dòng tiếp theo, dòng thứ ~i~ chứa hai số nguyên ~u_i, v_i~ ~(1≤u,v≤n; u≠v;)~ mô tả một cạnh của cây nối hai đỉnh ~u_i~ và ~v_i~.

Output

• In ra ~n~ số nguyên dương là độ đẹp của đường đi ~(1,u)~ với ~u \in [1,n]~

Subtask

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

Sample Input 1

3
6 2 3
1 2
1 3

Sample Output 1

6 6 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~

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