Đi tìm kho báu

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ở được 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. Như vậy mỗi chìa khóa mở nhiều nhất một hộp, mỗi hộp được mở bởi nhiều nhất một chìa khóa. Hai chìa khóa khác nhau có thể cùng mở được một cặp hộp.

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).

Ban đầu Luffy có đủ cả $k$ chìa khóa.

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. Mỗi truy vấn chỉ thay đổi tập chìa khóa đang có; với mỗi truy vấn, cách mở hộp được chọn lại từ đầu (không phụ thuộc các truy vấn trước).

Dữ liệu vào

• Dòng đầu tiên chứa ba số nguyên dương $n,k,Q$ $(2\le n\le 2·{10}^5,1\le k,Q\le 2·{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$ hoặc hộp $b_i$.
• $Q$ dòng tiếp theo, mỗi dòng chứa hai số nguyên mô tả một truy vấn:
  • 1 $p_i$: truy vấn loại $1$, bỏ đi chìa khóa $p_i$ $(1\le p_i\le k)$. Dữ liệu đảm bảo chìa khóa này đang có trong tay Luffy.
  • 2 $p_i$: truy vấn loại $2$, thêm lại chìa khóa $p_i$ $(1\le p_i\le k)$. Dữ liệu đảm bảo chìa khóa này đã được bỏ đi trước đó và chưa được thêm lại.

Dữ liệu ra

Gồm $Q$ 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$.

Ràng buộc

• $2\le n\le 2·{10}^5$.
• $1\le k\le 2·{10}^5$, $1\le Q\le 2·{10}^5$.
• $1\le c_i\le {10}^9$.
• $1\le a_i,b_i\le n$, $a_i\ne b_i$.
• $1\le p_i\le k$.

Subtasks

• Subtask 1 ($20\%$ số điểm): $n,k,Q\le 16$.
• Subtask 2 ($30\%$ số điểm): $n,k,Q\le 2000$.
• Subtask 3 ($50\%$ số điểm): không có ràng buộc gì thêm.

Ví dụ