题目描述

小杨认为大于等于 $a$ 的完全平方数是"超级幸运数"，超级幸运数的倍数是"幸运数"。

对于一个正整数 $x$，小杨想知道它是不是幸运数。如果是幸运数，则输出 lucky；否则输出将 $x$ 不断加 $1$ 直到成为幸运数时得到的数（即最小的、大于等于 $x$ 的幸运数）。

输入格式

第一行包含两个正整数 $a$ 和 $N$，含义如题目描述所示。

接下来 $N$ 行，每行包含一个正整数 $x$，表示询问的数字。

输出格式

对于每个询问，输出一行：

• 如果 $x$ 是幸运数，输出 lucky；
• 否则，输出最小的、大于等于 $x$ 的幸运数。

样例输入 #1

2 4
1
4
5
9

样例输出 #1

4
lucky
8
lucky

样例解释 #1

• $x=1$：大于等于 $1$ 的最小幸运数是 $4$（因为 $4=2^2$ 是超级幸运数，也是幸运数）。
• $x=4$：$4=2^2$ 是超级幸运数，也是幸运数，输出 lucky。
• $x=5$：大于等于 $5$ 的最小幸运数是 $8$（因为 $8$ 是 $4$ 的倍数，而 $4$ 是超级幸运数）。
• $x=9$：$9=3^2$ 是超级幸运数，也是幸运数，输出 lucky。

样例输入 #2

16 8
1
2
4
8
16
32
64
128

样例输出 #2

16
16
16
16
lucky
lucky
lucky
lucky

样例解释 #2

大于等于 $16$ 的完全平方数有 $16,25,36,49,\cdots$。

• 超级幸运数：$16,25,36,49,\cdots$
• 幸运数：超级幸运数及其倍数
• $1,2,4,8$ 都不是幸运数，但 $16$ 是大于等于它们的最小幸运数。
• $16,32,64,128$ 都是 $16$ 的倍数，而 $16$ 是超级幸运数，所以它们都是幸运数。

数据范围

$1 \le a \le 10^6$，$1 \le N \le 2 \times 10^5$，$1 \le x \le 1,000,001$。

知识点与难度

本题涉及的知识点从属于 GESP五级（数论、筛法思想），难度等级：⭐⭐。