Alice là một thủ kho quản lý lượng hàng hóa tại một kho vận lớn gồm \(N\) ngăn chứa hàng. Mỗi ngăn chứa ban đầu có một số lượng hàng hóa xác định. Trong quá trình vận hành, lượng hàng hóa có sự biến động liên tục. Để đối chiếu dữ liệu kế toán và kiểm tra sai sót, Alice cần khôi phục và truy vấn lượng hàng hóa tại các phiên bản lịch sử khác nhau.

Ban đầu, trạng thái kho hàng ở phiên bản số \(0\). Có \(Q\) sự kiện xảy ra tuần tự:

• 1 pos val: Thay đổi số lượng hàng hóa tại ngăn chứa \(pos\) thành \(val\). Thao tác này tạo ra một phiên bản kho hàng mới kế thừa trực tiếp từ phiên bản hiện tại.
• 2 v l r: Alice muốn tính tổng lượng hàng hóa trong các ngăn chứa từ chỉ số \(l\) đến chỉ số \(r\) ở phiên bản thứ \(v\).
• 3 v: Quay trở lại làm việc trên phiên bản kho hàng thứ \(v\) (các thay đổi sau đó sẽ kế thừa từ phiên bản này).

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

• Dòng đầu chứa hai số nguyên dương \(N\) và \(Q\) (\(1 \le N, Q \le 5 \cdot 10^4\)).
• Dòng hai chứa \(N\) số nguyên ban đầu của mảng đại diện cho số lượng hàng hóa tại các ngăn chứa.
• \(Q\) dòng tiếp theo chứa các yêu cầu.

Định dạng đầu ra

• Với mỗi yêu cầu loại 2, in ra tổng lượng hàng hóa trên một dòng riêng biệt.

Ví dụ

Input:

5 4
1 2 3 4 5
2 0 1 3
1 3 10
2 1 2 4
2 0 2 4

Output:

6
16
9