Cho dãy ~A~ gồm ~n~ số nguyên không âm, đánh số từ ~1~. Dãy tổng tiền tố ~B~ của ~A~ được định nghĩa như sau: $$\begin{cases} B_i = & & A_1, & i = 1 \\ B_i = B_{i - 1} & + & A_i, & 1 < i \le n \end{cases}$$

Tương tự, ta định nghĩa ~C~ là dãy tổng tiền tố của ~B~, và ~D~ là dãy tổng tiền tố của ~C~.

Cho ~q~ truy vấn, mỗi truy vấn thuộc một trong hai dạng:

• ~U~ ~x~ ~y~: gán ~A_x = y~.
• ~T~ ~w~: cho biết giá trị của ~T_w~, nói cách khác, phần tử thứ ~w~ của mảng ~T~.

trong đó:

~x~ và ~w~ là các chỉ số hợp lệ ~(1 \le x, w \le n)~.

~T~ là một trong ~3~ kí tự ~\{ B, C, D \}~, hay ~T \in \{ B, C, D \}~.

Yêu cầu:

Hãy viết chương trình thực hiện các truy vấn và trả lời các truy vấn hỏi giá trị.

Dữ liệu:

Nhập từ bàn phím gồm:

• Dòng đầu chứa một số nguyên ~n~ ~(1 \le n \le 4 \times 10^5)~, là số phần tử của dãy ~A~.
• Dòng tiếp theo chứa ~n~ số nguyên cách nhau bởi khoảng trắng là các phần tử của dãy ~A~.
• Dòng đầu chứa một số nguyên ~q~ ~(1 \le q \le 4 \times 10^5)~, là số truy vấn bạn cần xử lý.
• ~q~ dòng tiếp theo, mỗi dòng chứa một truy vấn thuộc một trong hai dạng đã nêu.

Các tham số của mỗi truy vấn cách nhau bởi một khoảng trắng.

Kết quả:

In ra màn hình một dòng cho mỗi truy vấn cho mỗi truy vấn loại ~2~. Vì kết quả có thể rất lớn, bạn cần đưa ra phần dư của kết quả khi chia cho ~10^9 + 7~.

Sample Input:

4
1 7 0 9
5
B 3
C 2
D 4
U 2 5
D 4

Sample Output:

8
9
61
49

Giải thích:

Trước truy vấn thứ ~4~, ta có các dãy ~A, B, C, D~ như sau:

Ràng buộc:

• Tại mọi thời điểm, các phần tử của ~A~ có giá trị không vượt quá ~10^9~.
• ~20\%~ số điểm của bài tương ứng với các test có ~T \in \{ B \}~.
• ~30\%~ số điểm khác của bài tương ứng với các test có ~T \in \{ B, C \}~.