Truy vấn sao chép
Cho một dãy $A$ chứa các dãy có độ dài bằng nhau và bằng $N$. Ban đầu, dãy $A$ chứa 1 dãy $t_1,t_2,...,t_N$. Có tất cả $Q$ truy vấn. Mỗi truy vấn thuộc 1 trong 3 loại sau:
1 k a x: Cập nhật phần tử thứ $a$ của dãy thứ $k$ thành $x$.2 k a b: Tính tổng các phần tử trong đoạn $[a,b]$ của dãy thứ $k$.3 k: Tạo 1 bản sao của dãy thứ $k$ và thêm vào cuối dãy $A$.
Dữ liệu
- Dòng đầu tiên chứa 2 số nguyên $N, Q \ (1\le N, Q \le 2\times 10^5)$;
- Dòng tiếp theo chứa $N$ số nguyên $t_i \ (1\le t_i \le 10^9)$;
- $Q$ dòng tiếp theo, mỗi dòng chứa một truy vấn theo mẫu trên $(1\le a \le b\le N; 1 \le x \le 10^9; k$ không vượt quá kích thước của dãy $A)$.
Kết quả
- In kết quả của mỗi truy vấn loại 3 trên mỗi dòng.
Ví dụ
Ví dụ 1
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
output
13
13
13
15
Comments