Cho dãy \(a_1, a_2, \ldots, a_n\) gồm các số tự nhiên. Tổng tiền tố tại vị trí \(i\) là tổng \(a_1 + a_2 + \ldots + a_i\), các bạn hãy tính tổng của một đoạn con bất kỳ… đề bài cho vậy thì quá dễ rồi sao?! Quốc Anh nghĩ các bạn ai cũng làm được, nên cậu thay đổi đề bài một chút:

• Cho 2 số nguyên \(s, k\) bất kỳ, hãy tính tổng bắt đầu từ vị trí \(s\), với bước nhảy là \(k\) đến vị trí gần \(n\) nhất.
• Cụ thể hơn, với một truy vấn \((s, k)\), hãy tính tổng \(a_s + a_{s+k} + a_{s+2k} + \ldots + a_{s+pk}\) với \(p\) là số tự nhiên lớn nhất sao cho \(s + pk \leq n\).

Và để làm khó các bạn một chút, Quốc Anh muốn các bạn hãy tính kết quả cho nhiều truy vấn \((s, k)\) như vậy. Cậu cũng đã thêm một số thao tác thay đổi một giá trị của dãy số \(a\) trong các truy vấn.

Yêu cầu: In ra kết quả của mỗi truy vấn \((s, k)\).

Dữ liệu vào

• Dòng đầu tiên là hai số nguyên dương \(n, q\) \((n, q \leq 2 \times 10^5)\).
• Dòng thứ hai là \(n\) số nguyên không âm \(a_1, a_2, \ldots, a_n\) \((0 \leq a_i \leq 10^9)\).
• \(q\) dòng tiếp theo là các truy vấn:
  • 1 i v: cập nhật \(a_i = v\).
  • 2 s k: in ra tổng \(a_s + a_{s+k} + a_{s+2k} + \ldots + a_{s+pk}\).

Dữ liệu ra

In ra kết quả của mỗi truy vấn \((s, k)\).

Input 1

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

Output 1

38
17
32
11

Input 2

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

Output 2

3
3

Subtask:

• 10% test có \(n, q \leq 2000\).
• 20% test có \(k \geq \sqrt{n}\) với mọi truy vấn \((s, k)\).
• 20% test có \(k \leq 2\) với mọi truy vấn \((s, k)\).
• 10% test có \(k \leq 3\) với mọi truy vấn \((s, k)\).
• 15% test có \(k \leq 5\) với mọi truy vấn \((s, k)\).
• 25% test có \(k \leq 15\) với mọi truy vấn \((s, k)\).