Xét dãy số nguyên dương ~a_1,a_2,…,a_n (a_i \le 10^4 )~ và hai thao tác trên dãy.

1. Thao tác loại ~0~ với hai thông số ~i,x~. Thao tác này sẽ thay đổi phần tử ~a_i~ bằng số nguyên dương ~x (x \le 10^4)~;
2. Thao tác loại ~1~ với hai thông số ~L,R~. Gọi ~P~ là tích các số từ ~L~ đến ~R, S~ là số ước số của ~P~, thao tác này sẽ đưa ra phần dư trong phép chia ~S~ cho ~10^9+7)~.

Yêu cầu: Cho dãy số ~a_1,a_2,…,a_n~ và ~q~ thao tác, với mỗi thao tác loại ~1~ hãy đưa ra kết quả tương ứng.

Dữ liệu:

• Dòng đầu chứa số nguyên ~n~;
• Dòng thứ hai chứa ~n~ số nguyên dương ~a_1,a_2,…,a_n~;
• Dòng thứ ba chứa số nguyên ~q~ là số thao tác;
• Tiếp theo là ~q~ dòng, mỗi dòng chứa ba số mô tả các thao tác. Cụ thể: nếu là thao tác loại ~0~ thì dòng gồm ba số ~0,i,x~; còn nếu là thao tác loại ~1~ thì dòng gồm ba số ~1,L,R~.

Kết quả:

• Ghi ra ~q~ dòng, mỗi dòng là một số tương ứng với kết quả cần đưa ra của các thao tác loại ~1~ theo thứ tự xuất hiện trong dữ liệu vào.

Ràng buộc:

• Có ~30\%~ số lượng test ứng với ~30\%~ số điểm có ~n=1;q \le 10~;
• Có ~30\%~ số lượng test khác ứng với ~30\%~ số điểm có ~n \le 10;q \le 10^5~;
• Có ~40\%~ số lượng test còn lại ứng với ~40\%~ số điểm có ~n \le 10^5;q \le 10^5~.

Ví dụ:

Sample Input

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

Sample Output

6
4