Băng Mũ Rơm của Luffy đã đặt chân đến hòn đảo Laugh Tale, nơi chứa kho báu ONE PIECE. Luffy tìm thấy ~n~ chiếc hộp, chiếc hộp thứ ~i~ chứa các đồ có giá trị ~c_i~. Trong tay Luffy có ~k~ chiếc chìa khóa được đánh số từ ~1~ đến ~k~. Chìa khóa thứ ~i~ có thể được dùng để mở một trong hai chiếc hộp ~a_i~ hoặc ~b_i~.

Mỗi chiếc hộp chỉ có thể được mở khóa một lần và không cần thiết phải dùng tất cả các chìa khóa.

Luffy chỉ được thực hiện ~Q~ truy vấn, truy vấn thứ ~i~ là yêu cầu thuộc một trong hai loại:

• Bỏ đi chiếc chìa khóa thứ ~p_i~; các chìa khóa còn lại không được đánh số lại sau các truy vấn.

• Thêm lại chiếc chìa khóa ~p_i~ đã bị bỏ đi trước đó; các chìa khóa còn lại không cần đánh số lại.

Yêu cầu: Hãy cho biết, sau khi thực hiện mỗi truy vấn, dùng các chìa khóa còn lại để mở hộp, với cách mở khóa hộp luôn tối ưu, tổng giá trị kho báu lớn nhất thu được từ các hộp được mở là bao nhiêu.

Input

• Dòng đầu tiên chứa ba số nguyên dương ~n,k,Q~ ~(2 \le n \le 2 \cdot 10^5, 1 \le k,Q \le 2 \cdot 10^5)~ là số hộp kho báu, số chìa khóa và số truy vấn.

• Dòng tiếp theo gồm ~n~ số nguyên dương ~c_1,c_2,\dots,c_n~ ~(c_i \le 10^9)~, là giá trị của các hộp kho báu.

• ~k~ dòng tiếp theo, dòng thứ ~i~ gồm hai số nguyên dương ~a_i,b_i~ ~(1 \le a_i,b_i \le n, a_i \ne b_i)~, mô tả chiếc chìa khóa thứ ~i~ mở được hộp ~a_i,b_i~.

• ~Q~ dòng tiếp theo, mỗi dòng chứa hai số nguyên mô tả các truy vấn:

  • 1 p_i: Cho biết đây là truy vấn loại ~1~ với chìa khóa bị bỏ đi là ~p_i~ ~(1 \le p_i \le n)~.

  • 2 p_i: Cho biết đây là truy vấn loại ~2~ với chìa khóa được thêm là ~p_i~. Dữ liệu đảm bảo chìa khóa này đã được bỏ đi trước đó.

Output

Gồm ~k~ dòng, dòng thứ ~i~ gồm một số nguyên là tổng giá trị kho báu lớn nhất thu được sau khi thực hiện truy vấn thứ ~i~.

Scoring

Sample Input 1

4 4 4
9 5 7 2
1 2
2 3
3 1
1 4
1 4
1 1
2 1
1 2

Sample Output 1

21
16
21
16

Notes

• Sau truy vấn thứ nhất, còn lại các chìa khóa ~1,2,3~. Ta có thể dùng chìa ~1~ để mở hộp ~2~, chìa ~2~ để mở hộp ~3~ và chìa ~3~ để mở hộp ~1~. Tổng giá trị của các hộp được mở là ~9+5+7=21~.

• Sau truy vấn thứ hai, còn lại chìa khóa ~2~ và ~3~. Ta có thể dùng chìa ~2~ để mở hộp ~3~, chìa ~3~ để mở hộp ~1~. Tổng giá trị của các hộp được mở là ~9+7=16~.

• Sau truy vấn thứ ba, còn lại các chìa khóa ~1,2,3~. Giống truy vấn một, tổng giá trị của các hộp được mở là ~9+5+7=21~.

• Sau truy vấn thứ tư, chỉ còn lại chìa khóa ~1~ và ~3~. Tổng giá trị các hộp mở được là ~9+7=16~.