题目描述

小杨认为，所有大于等于 $a$ 的完全平方数都是他的超级幸运数。

同时，所有超级幸运数的倍数也都是幸运数。特别地，超级幸运数本身也属于幸运数。

对于一个非幸运数，小杨会不断对它执行 $+1$ 操作，直到它变成一个幸运数。这个过程称为幸运化。

例如，当 $a=4$ 时，$4$ 是最小的幸运数。数字 $1$ 不是幸运数，但可以连续进行 $3$ 次 $+1$ 操作，使其变为 $4$，因此 $1$ 幸运化后的结果为 $4$。

现在给出 $N$ 个正整数，请判断它们是否为幸运数。对于不是幸运数的数，请输出它幸运化后的结果。

输入格式

第一行输入两个正整数 $a$ 和 $N$。

接下来 $N$ 行，每行输入一个正整数 $x$，表示需要判断或幸运化的数。

输出格式

输出 $N$ 行。

对于每个给定的 $x$：

• 如果 $x$ 是幸运数，输出 lucky；
• 否则输出 $x$ 幸运化后的结果。

样例

2 4
1
4
5
9

4
lucky
8
lucky

16 11
1
2
4
8
16
32
64
128
256
512
1024

16
16
16
16
lucky
lucky
lucky
lucky
lucky
lucky
lucky

样例解释

样例 $1$ 中：

$1$ 虽然是完全平方数，但由于 $1<a$，因此它不是超级幸运数，也不是幸运数。连续执行 $3$ 次 $+1$ 操作后得到 $4$，所以输出 $4$。

$4$ 是幸运数，因此输出 lucky。

$5$ 不是幸运数，连续执行 $3$ 次 $+1$ 操作后得到 $8$，所以输出 $8$。

$9$ 是幸运数，因此输出 lucky。

数据范围

对于 $30$ 的测试数据：

$a,x \le 100$，$N \le 100$。

对于 $60$ 的测试数据：

$a,x \le 10^6$。

对于所有测试数据：

$a \le 1000000$。

$N \le 2 \times 10^5$。

$1 \le x \le 1000001$。