Hash Pool Sum Query

Given a sequence of positive integers \(value\), each element \(value_k\) is stored in a hash pool according to its index modulo \(p\), i.e. it is stored in pool \(k \bmod p\). This can result in many collisions.

B will perform two types of operations:

• Update Operation: Change the value of an element \(value_k\). The change takes effect immediately.
• Query Operation: Given two integers \(p\) and \(x\) (with \(1 \le p < n\) and \(0 \le x < p\)), output the sum of all numbers in the pool \(x\) when indices are taken modulo \(p\). That is, compute \[ \sum_{k \text{ such that } k \bmod p = x} value_k. \]

All operations must be processed in the order given, with updates affecting subsequent queries immediately.

inputFormat

The first line contains two integers \(n\) and \(q\) separated by a space, where \(n\) is the number of elements in the array and \(q\) is the number of operations.

The second line contains \(n\) positive integers representing the initial values of the array.

Each of the next \(q\) lines describes an operation in one of the following formats:

• 1 i v: Update operation. Replace the element at index \(i\) (0-indexed) with the new value \(v\).
• 2 p x: Query operation. For the given modulus \(p\) and integer \(x\) (with \(0 \le x < p\)), output the sum of all elements whose index modulo \(p\) equals \(x\).

It is guaranteed that \(1 \le p < n\).

outputFormat

For each query operation (lines starting with 2), output a single line containing the sum of the elements in the specified pool.

sample

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

7
15
12