Công ty V và công ty H là hai công ty có truyền thống kình địch với nhau. Mỗi công ty đều có những tình báo của mình ở công ty đối phương nhằm thu thập thông tin cũng như đánh cắp những dữ liệu quan trọng cho công ty của mình.

Một điệp viên của công ty V đã tìm cách xâm nhập được vào hệ thống máy chủ của công ty H. Anh nhận ra rằng dữ liệu bí mật của công ty H thực chất là một dãy số nguyên dương \(A_1, A_2, \ldots, A_N\). Anh ta đã ghi lại được dãy số tại thời điểm xâm nhập hệ thống và đã cài đặt được một phần mềm có khả năng báo cáo toàn bộ các hoạt động của các thành viên của công ty H trên hệ thống dữ liệu.

Sau một thời gian, các thành viên của công ty V đã nhận được dãy số \(A\) và báo cáo về các thao tác trên cơ sở dữ liệu của công ty H. Công ty V sẽ tiến hành phân tích các thao tác này. Biết rằng, từ thời điểm hệ thống bị xâm nhập đến khi công ty V bắt đầu tiến hành phân tích, các thành viên của công ty H đã tiến hành \(Q\) thao tác trên hệ thống dữ liệu. Các thao tác này có thể được chia thành ba loại sau (quy ước thao tác thứ nhất là thao tác đầu tiên của công ty H trên cơ sở dữ liệu sau khi bị xâm nhập):

• Loại 1: thay đổi giá trị một phần tử \(A_V = H\).
• Loại 2: tính tổng \(A_L + A_{L+D} + A_{L+2D} + \cdots + A_{L+PD}\).
• Loại 3: khôi phục dãy \(A\) về trạng thái trước thao tác thứ \(T\).

Các thao tác được thực hiện tuần tự và được sắp xếp trong bản báo cáo theo thứ tự thời gian.

Yêu cầu: Từ dữ liệu về dãy \(A\) và bản báo cáo các thao tác, bạn hãy giúp công ty V khôi phục lại kết quả trả về của các thao tác loại 2.

Input

• Dòng đầu tiên gồm hai số nguyên dương \(N, Q\) \((1 \leq N, Q \leq 10^5)\).
• Dòng tiếp theo gồm \(N\) số nguyên dương \(A_1, A_2, \ldots, A_N\) \((1 \leq A_i \leq 10000)\).
• \(Q\) dòng tiếp theo là các thao tác trong bản báo cáo, mỗi dòng thuộc một trong ba dạng sau:
  • 1 V H: thao tác loại 1, với \(V, H\) là các số nguyên dương, yêu cầu thay đổi \(A_V = H\) \((1 \leq V \leq N,\ 1 \leq H \leq 10000)\).
  • 2 L P D: thao tác loại 2, với \(L, P, D\) là các số nguyên không âm, yêu cầu tính tổng \(A_L + A_{L+D} + A_{L+2D} + \cdots + A_{L+PD}\) \((1 \leq L \leq L + PD \leq N,\ 1 \leq D \leq N)\).
  • 3 T: thao tác loại 3, với \(T\) là một số nguyên dương, yêu cầu khôi phục dãy \(A\) về trạng thái trước thao tác thứ \(T\). Dữ liệu đầu vào đảm bảo thứ tự của thao tác hiện tại không nhỏ hơn \(T\).

Output

• Với mỗi thao tác loại 2, in ra kết quả trên một dòng.

Example

5 5
1 2 3 4 5
1 1 4
2 1 1 2
3 1
1 2 5
2 2 3 1

7
17

5 3
4 2 5 3 1
1 3 2
1 4 4
2 1 2 2

7

Scoring

• \(15\%\) số điểm không có thao tác loại 3 và \(P = 0\) với mọi thao tác loại 2.
• \(20\%\) số điểm khác có \(N, Q \leq 5000\).
• \(15\%\) số điểm khác không có thao tác loại 1 và \(D = 1\) với mọi thao tác loại 2.
• \(15\%\) số điểm khác không có thao tác loại 3 và \(D = 1\) với mọi thao tác loại 2.
• \(10\%\) số điểm khác không có thao tác loại 1.
• \(10\%\) số điểm khác có \(P = 0\) với mọi thao tác loại 2.
• \(5\%\) số điểm khác có \(D = 1\) với mọi thao tác loại 2.
• \(5\%\) số điểm khác không có thao tác loại 3.
• \(5\%\) số điểm còn lại không có giới hạn gì thêm.