Steve không thích làm các bài tập về số học lắm, đặc biệt là các bài tìm số lượng ước số. Thật không may, trước kỳ nghỉ Tết thầy giáo cho một loạt các bài tập tìm số lượng ước số của một tích các số nguyên. Steve không thể nào hiểu nổi, làm sao thầy giáo có thể nghĩ ra nhiều bài thế và làm thế nào để kiểm tra tính đúng đắn các bài làm của học sinh.

Nhìn đi nhìn lại các bài tập đáng ghét đó chợt Steve phát hiện ra mọi bài đều xuất phát từ một dãy số nguyên ~A~ ban đầu, ~A= (a_1, a_2, ..., a_n)~. Những bài khác nhau chỉ khác nhau một vài số ~a_i~ nào đó và phạm vi tính tích: từ ~a_l~ đến ~a_r~. Như vậy tất cả các bài tập phải làm có thể đưa về một bài tập Tin học xử lý dãy số ~A~ với 2 loại truy vấn:

~0~ ~i~ ~x~ - thay ~a_i~ bằng ~x~,

~1~ ~l~ ~r~ - tìm số lượng ước số của tích các phần tử ~a_l~ đến ~a_r~ và đưa kết quả ra theo mô đun ~10^9+7~.

Và thế là anh bạn láu lĩnh Steve trong vòng một tiếng đồng hồ giải quyết xong tất cả các bài tập của cả kỳ nghỉ Tết. Nhưng nếu là bạn, có thể bạn không cần nhiều thời gian đến thế?

Dữ liệu vào

Dòng đầu tiên chứa số nguyên ~n~ (~1 \leq n \leq 5 \times 10^4~),

Dòng thứ hai chứa ~n~ số nguyên ~a_1, a_2, ..., a_n~ (~1 \leq a_i \leq 10^4, i=1 \div n~),

Dòng thứ ba chứa số nguyên ~q~ - số lượng truy vấn (~1 \leq q \leq 10^4~),

Mỗi dòng trong ~q~ dòng tiếp theo chứa ~3~ số nguyên xác định một truy vấn, trong mọi truy vấn đảm bảo là ~1 \leq i, l, r \leq n, l \leq r, 1 \leq x \leq 10^4~.

Kết quả ra

Kết quả ứng với truy vấn tìm số lượng, mỗi kết quả trên một dòng.

Sample Input

5
2 3 4 5 6
6
1 2 4
1 2 3
0 1 1
0 4 7
1 1 3
1 1 4

Sample Output

12
6
6
12

Nguồn: Thầy Nguyễn Thanh Tùng