N. Суммы по остаткам

Дан массив $a_1, \ldots, a_n$. Два типа операций: прибавить число к одному элементу и узнать сумму всех $a_i$, у которых индекс даёт остаток $r$ при делении на $m$.

Здесь корневая работает не по индексам, а по величине шага. Заметим, что два случая устроены по-разному:

• шаг $m$ большой - индексов $r, r + m, r + 2m, \ldots$ мало, их всего $n / m$, и запрос можно честно просуммировать;
• шаг $m$ маленький - индексов много, зато самих маленьких шагов немного, и ответы можно держать готовыми.

В первой строке - числа $n$ и $q$ ($1 \le n, q \le 10^5$).

Во второй строке - $n$ чисел $a_i$ ($|a_i| \le 10^9$).

В следующих $q$ строках - операции. «1 i v» - прибавить $v$ к $a_i$ ($1 \le i \le n$, $|v| \le 10^4$). «2 m r» - сумма $a_i$ по всем $i$ с $i \bmod m = r$ ($1 \le m \le n$, $0 \le r < m$).

Индексы нумеруются с единицы. И значения в массиве, и ответы помещаются в 64-битный тип, но не в 32-битный: один элемент может собрать все $10^5$ прибавлений.

Для каждого запроса второго типа выведите сумму в отдельной строке.