题目描述

题目译自 XXIX Olimpiada Informatyczna – II etap Liczby względnie pierwsze

最近，Bajtazar 迷上了互质数的研究。所谓自然数 $x$ 与自然数 $y$ 互质，是指它们的最大公约数为 $1$。例如，与 $10$ 互质的数字包括：

$1, 3, 7, 9, 11, 13, 17, \ldots$

Bajtazar 将所有与数字 $n$ 互质的数字按升序写了出来，把这个列表装裱起来，从此称之为「Bajtazar 列表」。

在将这份作品挂上墙前，他想先检查一下列表的正确性。由于这个列表是无穷长的，他决定只抽查其中一段长度为 $c$ 的片段，从第 $k$ 个位置开始。列表中的元素从 $1$ 开始依次编号。你愿意帮助他完成这个任务吗？

输入格式

输入的第一行包含三个自然数 $n$, $k$, $c$ ($2 \leq n \leq 10^{14}$, $1 \leq k \leq 10^{14}$, $1 \leq c \leq 100000$)，分别表示 Bajtazar 选定的数字、检查片段的起始位置以及片段的长度。

输出格式

你的程序应输出一行，包含 $c$ 个自然数，用单个空格分隔，表示 Bajtazar 列表中第 $k$, $(k+1)$, $(k+2)$, $\ldots$, $(k+c-1)$ 个位置上的元素。提醒一下，这个列表包含所有与 $n$ 互质的数字，按升序排列。

样例 1

输入

10 3 4

输出

7 9 11 13

解释：Bajtazar 询问列表中第 $3$, $4$, $5$, $6$ 个位置的元素。对于 $n=10$，Bajtazar 列表依次为 $1$, $3$, $7$, $9$, $11$, $13$, $17$, $\ldots$。

样例 2 见附加文件下 lic1.in 和 lic1.out。

该样例满足 $n=2^{15}$, $k=1000$, $c=15300$；

样例 3 见附加文件下 lic2.in 和 lic2.out。

该样例满足 $n=257040$, $k=100$, $c=100$；

样例 4 见附加文件下 lic3.in 和 lic3.out。

该样例满足 $n$, $k$ 在 $[10^{13}, 10^{14}]$ 范围内随机，$c=100$；

样例 5 见附加文件下 lic4.in 和 lic4.out。

该样例满足 $n$, $k$ 在 $[10^{13}, 10^{14}]$ 范围内随机，$c=100000$。

数据范围与提示

详细子任务附加限制及分值如下表所示。

其中，$M$ 表示输出中最后一个数字，$f(n)$ 表示不超过 $n$ 且与 $n$ 不互质的数字个数。