P16607 [SYSUCPC 2025] Divisor Transformation

**Dr.Z** 正在研究一个长度为 $n$ 的排列 $p$（即 $p$ 包含从 $1$ 到 $n$ 的每个整数恰好一次）。他进行了 $q$ 次实验，每次实验由参数 $(l, r, x)$ 定义。 在每次实验中，他依次处理子数组 $p_l, p_{l+1}, \dots, p_r$。初始值为 $x$，对于子数组中的每个元素 $p_i$： - 若 $x \mid p_i$（$x$ 整除 $p_i$），则 $x$ 变为 $p_i / x$； - 否则，若 $p_i \mid x$（$p_i$ 整除 $x$），则 $x$ 变为 $x / p_i$； - 否则，$x$ 保持不变。 **Dr.Z** 需要你帮忙计算： - 处理完每次实验后 $x$ 的最终值； - 在整个处理过程中满足 $x \mid p_i$ 或 $p_i \mid x$ 的总次数。

第一行包含两个整数 $n, q$（$1 \le n, q \le 500000$）。 第二行包含 $n$ 个互不相同的整数 $p_1, p_2, \dots, p_n$（$\forall 1\le i\le n, 1\le p_i\le n$）。 接下来的 $q$ 行，每行包含 $3$ 个整数 $l, r, x$（$1 \le l \le r \le n, 1 \le x \le n$）。

对于每次实验，输出两个整数： - $x$ 的最终值； - 满足 $x \mid p_i$ 或 $p_i \mid x$ 的情况出现的总次数。

翻译由 DeepSeek V3.2 完成