FPT Bank vận hành hệ thống gộp tài khoản trực tuyến. Có \(N\) tài khoản, tài khoản thứ \(i\) có số dư ban đầu \(a_i\) (có thể âm nếu tài khoản thấu chi).

Sau mỗi thao tác gộp, số dư của nhóm bằng tổng số dư tất cả tài khoản trong nhóm. Hệ thống hỗ trợ:

• Gộp tài khoản: Hợp nhất nhóm chứa tài khoản \(u\) và nhóm chứa tài khoản \(v\) thành một nhóm chung.
• Hoàn tác: Phục hồi trạng thái trước thao tác gộp gần nhất (rollback). Nếu không có thao tác nào để hoàn tác, bỏ qua.
• Truy vấn tổng: Báo cáo tổng số dư của nhóm chứa tài khoản \(u\).

Định dạng đầu vào

• Dòng 1: Hai số nguyên \(N\) và \(Q\) (\(1 \le N, Q \le 10^5\)).
• Dòng 2: \(N\) số nguyên \(a_1, a_2, \ldots, a_N\) (\(-10^9 \le a_i \le 10^9\)).
• \(Q\) dòng tiếp theo:
  • 1 u v — Gộp nhóm chứa \(u\) và nhóm chứa \(v\).
  • 2 — Hoàn tác thao tác gộp gần nhất.
  • 3 u — In tổng số dư nhóm chứa \(u\).

Định dạng đầu ra

Với mỗi lệnh 3 u, in một số nguyên — tổng số dư nhóm chứa \(u\).

Ví dụ

Input:

4 7
10 20 30 40
1 1 2
3 1
1 3 4
3 3
2
3 1
3 3

Output:

30
70
30
30

Giải thích:

• Sau 1 1 2: nhóm {1,2} tổng 30; {3} tổng 30; {4} tổng 40.
• 3 1 → 30.
• Sau 1 3 4: nhóm {3,4} tổng 70.
• 3 3 → 70.
• 2: hoàn tác, quay về {3} và {4} riêng biệt.
• 3 1 → nhóm {1,2} vẫn gộp, tổng = 30.
• 3 3 → nhóm {3}, tổng = 30.

Ràng buộc

\(-10^9 \le a_i \le 10^9\), \(1 \le u, v \le N\).