Hái nấm

Tại xứ sở thần tiên, tương truyền rằng có một khu rừng nằm ở xứ Bắc có chứa loại nấm quý hiếm vô cùng giá trị.

Bạn---một người lữ hành trẻ tuổi, vừa đến khu rừng với mong muốn thu thập những cây nấm quý giá. Bằng công sức tìm kiếm của mình, bạn đã biết được vị trí của những cây nấm trong khu rừng này. Điều đặc biệt là khu rừng hiện có \(N\) cây nấm được đánh số từ \(1\) đến \(N\). Các cây nấm mọc trên một đường thẳng, và cây thứ \(i\) có giá trị là \(a[i]\).

Bạn sẽ ở lại khu rừng này trong \(Q\) ngày.

Mỗi ngày, sẽ có một trong hai sự kiện sau xảy ra:

• Giá trị của cây nấm thứ \(i\) trở thành \(u\). Bạn không thu thập nấm vào ngày này.
• Bạn sẽ bắt đầu thu thập tại cây nấm thứ \(j\). Tiếp theo đó đi về bên phải và liên tục bỏ qua \(k-1\) cây nấm khác. Thu thập cây nấm thứ \(j+k\) và cứ tuân thủ quy luật như vậy cho đến khi bạn đi hết dãy nấm. Hỏi đến cuối bạn sẽ nhặt được tổng giá trị là bao nhiêu.
  \end itemize

Ví dụ:
Có \(5\) cây nấm với giá trị lần lượt là dãy \([3, 2, 1, 4, 4]\).
Khi bạn bắt đầu từ cây nấm thứ \(1\) và \(k=2\) thì bạn sẽ thu thập các cây \(1,3,5\). Khi đó tổng giá trị nhặt được là \(8\).

Input

• Dòng đầu tiên chứa một số nguyên dương \(n\) \((n \leq 2 \times 10^{5})\) - số lượng cây nấm trong khu rừng.

• Dòng thứ hai chứa \(n\) số nguyên \(a_{1}, a_{2}, \ldots, a_{n}\) \((0 \leq a_{i} \leq 10^{9})\) -- giá trị của \(N\) cây nấm.

• Dòng thứ ba chứa một số nguyên dương \(q\) \((q \leq 10^{5})\) -- số ngày bạn sẽ ở lại.

• \(q\) dòng tiếp theo, mỗi dòng có một trong hai dạng sau:
  \begin itemize

• \(1\) \(i\) \(u\): cập nhật giá trị cây nấm thứ \(i\) trở thành \(u\).
• \(2\) \(j\) \(k\): nếu bắt đầu tại \(j\), thì theo quy luật trên, bạn sẽ thu thập được tổng giá trị là bao nhiêu.

Output

In ra đáp án cho sự kiện loại \(2\).

Example

7
7 9 2 3 2 9 8
5
2 4 2
1 2 3
2 5 1
2 2 3
2 5 3

12
19
5
2

Scoring

\begin itemize

• Có \(20\%\) số điểm: \(n, q \leq 2000\).
• Có \(40\%\) số điểm ứng với không có sự kiện loại 1.
• Có \(40\%\) số điểm: không có rằng buộc gì thêm.
  \end itemize