G. Modular Sorting

G. Modular Sorting

问题

给定一个整数 $m$ ( $2 \leq m \leq 5 \cdot 10^5$ ) 和一个由严格小于 $m$ 的非负整数组成的数组 $a$ 。

你需要处理两种类型的查询：

i x: 赋值 $a_i := x$ (此操作会持久更新数组)。
k: 在一次操作中，你可以选择任意元素 $a_i$ 并赋值 $a_i := (a_i + k) \bmod m$ 。判断是否存在一个这样的操作序列（可能为零次），可以使数组变为 非递减 的（即 $a_0 \leq a_1 \leq \dots \leq a_{n-1}$ ）。

注意：类型 2 的查询是 假设性 的 — 它们不会修改数组。类型 1 的查询是 持久性 的，会永久改变数组。

对于一个参数为 $k$ 的类型 2 查询，我们的目标是判断是否存在一组非负整数 $t_0, t_1, \dots, t_{n-1}$ 使得：

a_i' = (a_i + t_i \cdot k) \bmod m

并且得到的数组 $a'$ 是非递减的。

令 $g = \gcd(k, m)$ 。当我们重复应用操作 $a_i := (a_i + k) \bmod m$ 时， $a_i$ 可以达到的值都位于同一个 模 $g$ 的陪集 中：

a_i' \equiv a_i \pmod{g}

这意味着 每个元素在任何次数的以 $k$ 为步长的操作下，其模 $g$ 的余数保持不变。

因此，任意两个元素 $a_i$ 和 $a_j$ 之间的最小差值为 $(a_j - a_i) \bmod g$ 。

那么， $a_i$ 的所有可达值构成了这个长度的循环群。为了检查我们是否能将值重新排列成非递减顺序，我们使用一个关键指标，该指标衡量从左到右需要多少模“增量”。

我们定义：

S(g) = \sum_{j=0}^{n-1} \Delta_j

其中

这个表达式捕捉了在模 $g$ 下从 $a_{j-1}$ 移动到 $a_j$ 所需的“正模步长”。

对于一个给定 $k$ 的类型 2 查询，令 $g = \gcd(k, m)$ 。那么：

当且仅当 $S(g) < m$ 时，数组可以变为非递减。

如果 $S(g) \geq m$ ，所需的模位移将会环绕 $m$ — 违反了非递减约束。

当处理一个类型 1 查询 (i x) 时，我们需要为 $m$ 的 所有因子 $g$ 更新指标 $S(g)$ ，因为任何未来的查询都可能使用一个 $k$ 使得 $\gcd(k, m) = g$ 。

将 $a_i$ 更改为 $x$ 最多影响 $S(g)$ 中的两项：

对于每个这样的 $g$ ，我们：

为了保持效率，我们：