Nhiệm vụ của bạn là duy trì một danh sách các mảng, danh sách ban đầu chỉ có một mảng duy nhất. Bạn phải xử lý các loại truy vấn sau:

1. Gán giá trị \(a\) trong mảng \(k\) thành \(x\).
2. Tính tổng các giá trị trong đoạn \([a,b]\) trong mảng \(k\).
3. Tạo một bản sao của mảng \(k\) và thêm nó vào cuối danh sách.

Input

• Dòng đầu tiên chứa hai số nguyên \(n\) và \(q\): kích thước của mảng và số lượng truy vấn.
• Dòng tiếp theo chứa \(n\) số nguyên \(t_1, t_2, \dots, t_n\): các giá trị ban đầu của mảng.
• \(q\) dòng cuối cùng mô tả các truy vấn. Định dạng của từng truy vấn là một trong các kiểu sau: 1 k a x, 2 k a b or 3 k.

Output

• In ra kết quả của từng truy vấn tính tổng.

Constraints

• \(1 \le n, q \le 2 \times 10^5\)
• \(1 \le t_i, x \le 10^9\)
• \(1 \le a \le b \le n\)

Example

Sample input

5 6
2 3 1 2 5
3 1
2 1 1 5
2 2 1 5
1 2 2 5
2 1 1 5
2 2 1 5

Sample output

13
13
13
15