题目描述

小杨定义了一种新的幸运数：一个数如果满足以下两个条件，则被称为幸运数：

1. 它是某个大于等于 a 的完全平方数
2. 它分解质因数后，所有质因数的指数都是偶数

现在给定 N 个数，请你判断每个数是否为幸运数。

输入格式

第一行包含 2 个正整数 a, N。 接下来 N 行，每行一个正整数 x，表示需要判断的数。

输出格式

输出 N 行，对于每个给定的 x：

• 如果它是幸运数，输出 "lucky"
• 否则，输出 "unlucky"

样例 #1

样例输入 #1

4 4
8
9
12
16

样例输出 #1

unlucky
lucky
unlucky
lucky

样例解释 1

• 8 = 2³，质因数指数为奇数，不是幸运数
• 9 = 3²，是≥4的完全平方数9的因数，且质因数指数为偶数，是幸运数
• 12 = 2²×3¹，质因数3的指数为奇数，不是幸运数
• 16 = 4²，是≥4的完全平方数16的因数，且质因数指数为偶数，是幸运数

提示

数据规模

• 30%的测试点：a,x ≤ 100，N ≤ 100
• 60%的测试点：a,x ≤ 10⁶，N ≤ 10⁵
• 所有测试点：a ≤ 10⁶，N ≤ 2×10⁵，1 ≤ x ≤ 10⁶+1