题目内容

在一个长度为 $n$ 的正整数序列 $a_1, a_2, \dots, a_n$ 中（下标从 $1$ 开始），我们称两个整数 $x$ 和 $y$ 是 共鸣 的，如果它们的最大公约数大于 $1$，即 $\gcd(x, y) > 1$。

现在有 $q$ 个询问，每个询问给出两个整数 $p$ 和 $k$。对于每个询问，你需要从位置 $p$ 开始，向右依次检查每一个位置 $i$（$p \le i \le n$），统计满足 $a_p$ 与 $a_i$ 共鸣的 $i$ 的个数。当计数达到第 $k$ 个时，输出该位置的下标；如果扫描到末尾仍不足 $k$ 个，则输出 $-1$。

数据范围：序列长度 $n$ 和询问次数 $q$ 均不超过 $6 \times 10^4$，序列中的每个整数大小在 $2$ 到 $6 \times 10^4$ 之间。

输入描述

第一行包含两个整数 $n$ 和 $q$，分别表示序列长度和询问次数。 第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$，表示序列中的元素。