Truy vấn Đoạn và Sao chép

Bạn quản lý một danh sách các mảng, ban đầu chỉ có một mảng gồm $n$ phần tử. Bạn cần xử lý $q$ truy vấn thuộc ba loại:

1. Cập nhật: Gán giá trị tại vị trí $a$ trong mảng $k$ bằng $x$.
2. Tính tổng: Tính tổng các phần tử từ vị trí $a$ đến $b$ trong mảng $k$.
3. Sao chép: Tạo một bản sao của mảng $k$ và thêm vào cuối danh sách.

Dữ liệu vào

Dòng đầu chứa hai số nguyên $n$ và $q$: kích thước mảng ban đầu và số truy vấn.

Dòng thứ hai 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 tiếp theo, mỗi dòng mô tả một truy vấn:

• 1 k a x — gán $t_a=x$ trong mảng $k$

• 2 k a b — tính tổng từ $a$ đến $b$ trong mảng $k$
• 3 k — sao chép mảng $k$

Dữ liệu ra

Với mỗi truy vấn loại 2, in ra tổng tương ứng.

Ràng buộc

• $1\le n,q\le 2·{10}^5$
• $1\le t_i,x\le {10}^9$
• $1\le a\le b\le n$
• Mảng $k$ luôn tồn tại tại thời điểm truy vấn

Ví dụ