P16607 [SYSUCPC 2025] Divisor Transformation

$\texttt{Dr.Z}$ is studying a permutation $p$ of length $n$ (i.e., $p$ contains each integer from $1$ to $n$ exactly once). He performs $q$ experiments, each defined by parameters $(l, r, x)$. In each experiment, he processes the subarray $p_l, p_{l+1}, \dots, p_r$ sequentially. Starting with value $x$, for each element $p_i$ in the subarray: - If $x \mid p_i$ ($x$ divides $p_i$), then $x$ becomes $p_i / x$ - Else if $p_i \mid x$ ($p_i$ divides $x$), then $x$ becomes $x / p_i$ - Otherwise, $x$ remains unchanged $\texttt{Dr.Z}$ needs your help to compute: - The final value of $x$ after processing each experiment - The total number of times either $x \mid p_i$ or $p_i \mid x$ was satisfied during the process

The first line contains two integers $n,q\ (1 \le n, q \le 500000)$ The second line contains $n$ distinct integers $p_1, p_2, \dots, p_n\ (\forall 1\le i\le n,1\le p_i\le n)$ The next $q$ lines each contain 3 integers $l,r,x\ (1 \le l \le r \le n,1 \le x \le n)$

For each experiment, output two integers: - The final value of $x$ - The total count of cases where either $x \mid p_i$ or $p_i \mid x$