题目内容

给定一个长度为 $n$ 的正整数序列 $v_1, v_2, \dots, v_n$，下标从 $1$ 开始。定义两个位置 $i$ 和 $j$ 共鸣当且仅当 $v_i$ 与 $v_j$ 至少共享一个质因子。

现有 $q$ 次查询，每次查询给出两个整数 $p$ 和 $k$。对于每个查询，从位置 $p$ 开始向右依次扫描，找到第 $k$ 个与 $v_p$ 共鸣的位置，输出该位置的下标；若扫描到序列末尾仍不足 $k$ 个，则输出 $-1$。

约束条件

• 序列长度 $n$ 和查询次数 $q$ 均不超过 $6 \times 10^4$。
• 序列中的每个整数 $v_i$ 满足 $2 \le v_i \le 6 \times 10^4$。
• 对于每次查询，$1 \le p \le n$，$1 \le k \le n$。

输入描述

第一行包含两个整数 $n$ 和 $q$，表示序列的长度和查询的次数。 第二行包含 $n$ 个整数 $v_1, v_2, \dots, v_n$，表示各位置的值。 接下来 $q$ 行，每行包含两个整数 $p$ 和 $k$，表示一次查询的起始位置与目标序号。

输出描述

对于每次查询，输出一行一个整数，表示第 $k$ 个共鸣位置的下标（从 $1$ 开始）；若不存在则输出 $-1$。

样例1

输入

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

输出

3
2
5

说明

• 查询1：$p=1$, $k=2$。$v_1=2$，质因子为 $\{2\}$。在区间 $[1,5]$ 中与 2 共鸣的位置为：$1$（值为 2）、$3$（值为 4）、$4$（值为 6）、$5$（值为 12）。从位置 $1$ 开始扫描，第 1 个共鸣位置是 $1$，第 2 个是 $3$，故输出 3。
• 查询2：$p=2$, $k=1$。$v_2=3$，质因子 $\{3\}$。区间 $[2,5]$ 中与 3 共鸣的位置有：$2$（3）、$4$（6）、$5$（12）。第 1 个位置为 $2$，输出 2。
• 查询3：$p=4$, $k=2$。$v_4=6$，质因子 $\{2,3\}$。区间 $[4,5]$ 中与 6 共鸣的位置有：$4$（6）、$5$（12）。第 2 个位置为 $5$，输出 5。

样例2

输入

6 3
7 11 13 14 22 15
1 2
2 3
3 1

输出

4
-1
3

说明

• 查询1：$p=1$, $k=2$。$v_1=7$，质因子 $\{7\}$。共鸣位置：$1$（7），$4$（14）。从 $1$ 向右，第 2 个共鸣位置是 $4$，输出 4。
• 查询2：$p=2$, $k=3$。$v_2=11$，质因子 $\{11\}$。共鸣位置：$2$（11），$5$（22）。区间 $[2,6]$ 内仅有 2 个共鸣位置，不足 $k=3$，输出 -1。
• 查询3：$p=3$, $k=1$。$v_3=13$，质因子 $\{13\}$。只有位置 $3$ 自身共鸣，输出 3。

样例3

输入

2 1
2 3
1 1

输出

1

说明

数组长度为 $2$，$a=[2,3]$。查询 $p=1$, $k=1$。从下标 $1$ 开始扫描，$\gcd(2,2)=2\neq1$，第 $1$ 个满足条件的位置就是 $1$，输出 1。