Hôm nay, những nhân vật thông minh nhất vũ trụ anime như \(Conan, Kira, L, Sakamoto, Armin, ...\) đang tranh giải "Bộ não vàng" do algorit tổ chức. bin9638 cũng là một trong những người tham gia cuộc thi này. Để chiến thắng cuộc thi thì phải giải được bài toán mà algorit đưa ra như sau:

Cho một dãy số nguyên dương \(A_1,A_2,...,A_N\) gồm \(N\) phần tử .

Cho \(Q\) thao tác , mỗi thao tác gồm 2 số nguyên dương \(x\) và \(y\) , thao tác này làm tất cả phần tử đang mang giá trị \(x\) trong mảng chuyển thành giá trị \(y\). Với mỗi thao tác hãy tính tổng tất cả các phần tử của mảng

bin9638 rất muốn trở thành nhân vật thông minh nhất vũ trụ anime nhưng vì những đối thủ của anh quá giỏi nên đành nhờ các bạn giúp đỡ. Hãy giúp cậu ấy nhé !

• Yêu cầu : Sau mỗi thao tác hãy tính lại tổng tất cả các phần tử của mảng .

Input

• Dòng đầu tiên gồm 2 số nguyên dương \(N\) và \(Q\) \(. (N , Q \le 10^6)\)
• Dòng tiếp theo gồm các số nguyên dương \(A_1,A_2,...,A_N\) \(. (A_i \le 10^{12})\)
• \(Q\) dòng tiếp theo gồm 2 số nguyên dương \(x , y\) \(. (x,y \le 10^{12})\)

Output

• Gồm \(Q\) dòng , mỗi dòng là tổng giá trị của mảng .

Scoring

• Subtask \(1\) (\(30\%\) số điểm): \(N,Q \le 10^3 , A_i \le 10^9.\)*
• Subtask \(2\) (\(30\%\) số điểm): \(N,Q \le 10^5 , A_i \le 10^6.\)*
• Subtask \(3\) (\(40\%\) số điểm): không có ràng buộc gì thêm .*

Example

5 3
1 2 3 5 4
1 2
2 3
3 4 

16
18
21