解题思路

对于一次查询 $(p, k)$，题目要求从下标 $p$ 开始向右扫描，找到第 $k$ 个满足

的位置 $i$。

题目内容

给定由 $n$ 个整数构成的数组 $\{a_1,a_2,\dots,a_n\}$，下标从 $1$ 到 $n$。现在有 $q$ 次查询，每次查询给出两个整数 $p,k$。

对于每个查询，定义如下过程：

• 从数组下标 $p$ 开始（包含该位置），依次向右扫描每个位置 $i\ (p \le i \le n)$
• 统计满足 $\gcd(a_p,a_i) \neq 1$ 的元素，当计数达到 $k$ 时，输出该位置的下标；
• 如果扫描结束仍未找到第 $k$ 个此类元素，则输出 $-1$。

最大公约数（gcd）定义：多个整数共有约数中最大的一个，例如 $\gcd(12,30)=6$。

输入描述

第一行输入两个整数 $n,q\ (2 \le n,q \le 6 \times 10^4)$，分别表示数组长度和查询次数；

第二行输入 $n$ 个整数 $a_1,a_2,\dots,a_n\ (2 \le a_i \le 6 \times 10^4)$；

接下来 $q$ 行，每行输入两个整数 $p,k\ (1 \le p \le n;\ 1 \le k \le n)$。

输出描述

对每次查询，新起一行输出一个整数，表示答案下标；若不存在，则输出 $-1$。

样例1

输入

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

输出

3
2
-1

说明

• 查询 $(1,2)$：起始元素 $a_1 = 2$，扫描位置依次为 $1$（$\gcd(2,2) = 2 \ne 1$，计数 $1$）、$2$（$\gcd(2,3) = 1$，跳过）、$3$（$\gcd(2,4) = 2 \ne 1$，计数 $2$），第 $2$ 个不互质元素为下标 $3$；

• 查询 $(2,1)$：起始元素 $a_2 = 3$，扫描位置 $2$（$\gcd(3,3) = 3 \ne 1$），第 $1$ 个不互质元素为下标 $2$；

• 查询 $(3,3)$：起始元素 $a_3 = 4$，扫描位置依次为 $3, 4$，仅计数到 $2$，不存在第 $3$ 个，输出 $-1$。