Danh sách thực đơn của nhà hàng Bluetaurant có tổng cộng ~n~ món ăn, món thứ ~i~ có giá ~p_i~ đồng. Trong vòng ~m~ ngày tiếp theo, mỗi ngày nhà hàng sẽ thực hiện sự kiện thay đổi giá thuộc một trong hai loại sau:

• Loại ~1~ có dạng SET x y ~(1 \le x,y \le 10^6)~ ~:~ Các món ăn có giá ~x~ đồng đều chuyển thành giá ~y~ đồng.
• Loại ~2~ có dạng INFLATION z ~(1 \le z \le 10^6)~ ~:~ Giá của các món ăn trong thực đơn đều tăng thêm ~z~ đồng.

Với mỗi ngày sau khi thực hiện sự kiện thay đổi giá, bạn hãy giúp nhà hàng tính tổng giá của tất cả các món ăn có trong thực đơn.

Input

• Dòng đầu tiên chứa số nguyên ~n~ ~(1 \le n \le 3 \times 10^5)~.
• Dòng thứ hai chứa ~n~ số nguyên ~p_i~ ~(1 \le p_i \le 10^6)~.
• Dòng tiếp theo chứa số nguyên ~m~ ~(1 \le m \le 10^5)~.
• ~m~ dòng tiếp theo, mỗi dòng chứa một sự kiện thuộc một trong hai loại trên.

Output

• Với mỗi ngày sau khi thực hiện sự kiện thay đổi giá, in ra trên một dòng là tổng giá của tất cả các món ăn có trong thực đơn.

Examples

Sample Input 1

4
1 2 3 4
3
SET 2 5
INFLATION 1
SET 4 1

Sample Output 1

13
17
14

Sample Input 2

7
3 5 8 2 6 9 2
5
SET 2 8
SET 8 9
INFLATION 3
INFLATION 1
SET 6 1

Sample Output 2

47
50
71
78
78

Scoring

• Subtask ~1~ ~-~ ~20\%~ số điểm: ~n=1~
• Subtask ~2~ ~-~ ~28\%~ số điểm: ~n,m,p_i,x,y,z \le 100~
• Subtask ~3~ ~-~ ~24\%~ số điểm: Không có sự kiện loại ~1~
• Subtask ~4~ ~-~ ~16\%~ số điểm: Không có sự kiện loại ~2~
• Subtask ~5~ ~-~ ~12\%~ số điểm: Không có ràng buộc gì thêm