N. Нули по остаткам

То же разбиение по величине шага, что в классной задаче N, но вместо суммы спрашивается количество нулей среди элементов с индексами нужного остатка.

Таблица zeros[m][r] для $m \le \sqrt{n}$ строится и обновляется так же, как таблица сумм. Разница в том, что обновление теперь не всегда что-то меняет.

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

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

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

Индексы нумеруются с единицы.

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