跳房子马拉松

2022 年 10 月 8 日。这是全国计算机科学专业的学生一年中最期待的日子。不，我们说的不是 ICPC。

我们当然是在说跳房子！对于不熟悉的人来说，跳房子是一项传统的年度竞赛，通常作为 ICPC 的附属活动举行。这项广受欢迎的儿童游戏的异国变体在无限的螺旋形场地上进行，场地被细分为从零开始依次编号的区域，如下图所示，并向各大洲的观众以及最深奥编程语言的从业者进行直播。

今年，跳房子比赛吸引了创纪录的 $N$ 名参赛者，编号从 $1$ 到 $N$。已知第 $i$ 名参赛者从编号为 $A_i$ 的区域开始。

跳房子比赛包含 $Q$ 轮。在第 $q$ 轮中，担任跳房子组织者已久的 Carlão 会向参赛者传达两个整数：$c_q$ 和 $d_q$。这是一个给所有编号为 $i$ 的参赛者的指令，如果 $i$ 和 $c_q$ 共享一个大于 $1$ 的公约数，则该参赛者需要在跳房子场地上向后移动 $d_q$ 个位置，一次移动一个位置，但绝不会退回到 $0$ 号位置之前。（任何最终回到 $0$ 号位置的参赛者应无限期地留在那里，忽略后续的任何后退指令，以免离开场地。）

假设参赛者完美地执行了指令（他们绝不会想让 Carlão 失望），你的任务是确定每位参赛者回到 $0$ 号位置的轮次（如果从未发生，则指出这一点）。

输入格式

第一行包含整数 $N$ 和 $Q$ ($1 \le N, Q \le 10^5$)。第二行包含 $N$ 个整数，即 $A_1, A_2, \dots, A_N$ ($1 \le A_i \le 10^9$)。接下来的 $Q$ 行，每行包含两个整数 $c_q$ 和 $d_q$ ($1 \le c_q \le 10^5, 1 \le d_q \le 10^9$)。

输出格式

你必须输出 $N$ 行。第 $i$ 行应包含一个整数，表示第 $i$ 名参赛者回到 $0$ 号位置的轮次（如果从未发生，则输出 $-1$）。

样例

样例输入 1

7 6
10 20 30 40 50 60 70
2 25
3 36
100 42
5 10
7 70
1 1000

样例输出 1

-1
1
2
3
4
2
5

样例输入 2

6 4
100 100 100 100 100 100
2 50
3 50
5 99
5 1

样例输出 2

-1
-1
-1
-1
4
2