模 M 约数

题目描述

给定两个正整数 $N$ 和 $M$。对每个 $k=0,1,\ldots,M-1$，求解以下问题：

判断是否存在满足下述条件的正整数 $t$，若存在，求出最小的 $t$。

• 存在 $N^t$ 的一个正约数 $x$，满足 $x \equiv k \pmod M$。

输入格式

输入一行两个整数 $N,M$。

输出格式

输出 $M$ 行。第 $i$ 行（$1 \le i \le M$）对应 $k=i-1$：如果存在满足条件的正整数 $t$，输出最小的 $t$；否则输出 $-1$。

6 7

-1
1
1
1
2
2
1

样例 1 解释

例如当 $k=3$ 时，$x=3$ 是 $N^1=6$ 的约数，且 $3 \equiv 3 \pmod 7$，所以满足条件的最小正整数是 $t=1$。

4 8

2
1
1
-1
1
-1
-1
-1

1 5

-1
1
-1
-1
-1

数据范围

对于所有测试数据，保证：

• $1 \le N \le 10^{14}$；
• $1 \le M \le 4 \times 10^5$；
• $N,M$ 均为整数。

子任务

本题共 20 个测试点，按测试点计分：

每个测试点单独评分，全部测试点的得分之和即为本题得分。