题目描述

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$ 的情况出现的总次数。

6 6
1 4 3 2 5 6
1 6 4
3 4 2
3 4 4
5 5 1
2 5 3
6 6 4

2 4
1 1
2 1
5 1
2 2
4 0

提示

翻译由 DeepSeek V3.2 完成