Cho dãy \(a_{1}, a_{2}, \ldots, a_{n}\) gồm các số tự nhiên. Cần thực hiện \(q\) truy vấn, mỗi truy vấn là một trong hai thao tác sau:

1. Nhập vào hai số nguyên \(i, u\) \((1 \leq i \leq n, 0 \leq u \leq 10^{9})\). Cập nhật \(a_{i} = u\).
2. Nhập vào hai số nguyên \(p, k\) \((1 \leq p, k \leq n)\). Hãy tính tổng \(a_{p} + a_{p + k} + a_{p + 2k} + \ldots + a_{p + uk}\) với u là số nguyên lớn nhất sao cho \(p + uk \leq n\).

Input

• Dòng đầu tiên chứa một số nguyên dương \(n\) \((n \leq 2 \times 10^{5})\).
• Dòng thứ hai chứa \(n\) số nguyên \(a_{1}, a_{2}, \ldots, a_{n}\) \((0 \leq a_{i} \leq 10^{9})\).
• Dòng thứ ba chứa một số nguyên dương \(q\) \((q \leq 2 \times 10^{5})\), số lượng truy vấn.
• \(q\) dòng tiếp theo, mỗi dòng có một trong hai dạng sau:
  • \(1\) \(i\) \(u\): cập nhật \(a_{i} = u\).
  • \(2\) \(p\) \(k\): in ra tổng \(a_{p} + a_{p + k} + a_{p + 2k} + \ldots\).

Output

• Với mỗi truy vấn 2, in ra đáp số trên một dòng.

Scoring

• Subtask \(1\) (\(20\%\) số điểm): \(n, q \leq 2000\).
• Subtask \(2\) (\(40\%\) số điểm): đều là loại 2 (không có truy vấn cập nhật).
• Subtask \(3\) (\(40\%\) số điểm): không có rằng buộc gì thêm.

Example

8
6 7 1 3 9 0 7 5
5
2 1 1
2 3 2
1 5 3
2 1 1
2 3 2

38
17
32
11