Problem Description

Xiao Yang believes that all perfect square numbers greater than or equal to \(a\) are his super lucky numbers.

Xiao Yang also believes that all multiples of his super lucky numbers are his lucky numbers. Naturally, all of Xiao Yang's super lucky numbers are also lucky numbers.

For a number that is not a lucky number, Xiao Yang stipulates that it can be incremented continuously until it becomes a lucky number. We call this process "luckyfication." For example, if \(a = 4\), then \(4\) is the smallest lucky number, and \(1\) is not, but we can increment \(1\) three times to make it \(4\), so we can say that the result of luckyfication for \(1\) is \(4\).

Now, Xiao Yang gives you \(N\) numbers, and you need to first determine if they are lucky numbers; then, for those that are not lucky numbers, you need to perform luckyfication on them.

Input Format

The first line contains two positive integers \(a, N\).

Next, \(N\) lines follow, each containing a positive integer \(x\), which is the number to be judged (or luckyfied).

Output Format

Output \(N\) lines. For each given \(x\), if it is a lucky number, output lucky; otherwise, output the result of its luckyfication.

Sample Input and Output

Sample Input #1

2 4
1
4
5
9

Sample Output #1

4
lucky
8
lucky

Sample Input #2

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

Sample Output #2

16
16
16
16
lucky
lucky
lucky
lucky
lucky
lucky
lucky

Notes

Sample Explanation 1

Although it is a perfect square number, it is less than \(a\), so it is not a super lucky number or a lucky number. After incrementing it three times, it finally becomes the lucky number \(4\). Since \(4\) is a lucky number, it directly outputs lucky.

\(5\) is not a lucky number. After incrementing it three times, it finally becomes the lucky number \(8\).

\(9\) is a lucky number, so it directly outputs lucky.

Data Size

For 30% of the test cases, it is guaranteed that \(a, x \leq 100, N \leq 100\).

For 60% of the test cases, it is guaranteed that \(a, x \leq 10^6\).

For all test cases, it is guaranteed that \(a \leq 1,000,000\); \(N \leq 2 \times 10^5\); \(1 \leq x \leq 1,000,001\).

见题面 Input 部分

见题面 Output 部分