K. Divisor Transformation
time limit per test
3 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

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

Dr.Z needs your help to compute:

  1. The final value of $$$x$$$ after processing each experiment
  2. The total number of times either $$$x \mid p_i$$$ or $$$p_i \mid x$$$ was satisfied during the process
Input

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

Output

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$$$
Example
Input
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
Output
2 4
1 1
2 1
5 1
2 2
4 0