题目描述

$\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$

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