Cho một tập các mảng mà ban đầu chỉ có một mảng. Nhiệm vụ của bạn là thực hiện các truy vấn sau:

• \(1\) \(k\) \(a\) \(x\): Thay đổi phần tử thứ \(a\) ở mảng thứ \(k\) thành \(x\).
• \(2\) \(k\) \(a\) \(b\): Tính tổng các phần tử trong đoạn \([a, b]\) ở mảng \(k\).
• \(3\) \(k\): Tạo một bản sao của mảng \(k\) và đưa vào cuối tập các mảng.

Input

• Dòng thứ nhất gồm hai số nguyên dương \(N, Q\): kích thước từng mảng và số truy vấn.
• Dòng thứ hai gồm \(N\) số nguyên dương \(A_1, A_2, ..., A_N\) \((1 \leq A_i \leq 10^9)\).
• \(Q\) dòng tiếp theo, mỗi dòng là một truy vấn thuộc một trong ba dạng sau:
  • \(1\) \(k\) \(a\) \(b\) \((1 \leq k \leq\) số mảng hiện tại, \(1 \leq a \leq b \leq N)\).
  • \(2\) \(k\) \(a\) \(b\) \((1 \leq k \leq\) số mảng hiện tại, \(1 \leq a \leq b \leq N)\).
  • \(3\) \(k\) (\(1 \leq k \leq\) số mảng hiện tại).

Output

• In ra kết quả cho các truy vấn \(2\).

Scoring

• Subtask \(1\) (\(50\%\) số điểm): \(N, Q \leq 2.10^3\).
• Subtask \(2\) (\(50\%\) số điểm) \(N, Q \leq 2.10^5\).-

Example

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 

13
13
13
15