1709：蒜头君的序列

蒜头君今天出门，在地上捡到了一个序列 a。

秉承着拾金不昧的原则，蒜头君在原地等待序列 a 的主人回来，并将序列还给他。

但是蒜头君十分喜欢这个序列，在等待的过程中，蒜头君拿出一个初始序列，这个初始序列的长度与序列 a 的长度相等，且每个数字都为 0。蒜头君可以对这个初始序列进行操作。对于第 i 次操作：

• 可以选定初始序列中的任意位置，将其加上kⁱ ( i 从 0 开始）
• 什么也不做。

如果可以，则输出 ^_^ ; 否则输出 QwQ。

第一行输入一个正整数 T, 表示测试的组数。

接下来输入 T 组数据。

对于每组数据：

第一行输入两个整数 n, k, 分别表示序列长度和题面中的 k。

第二行输入 n 个正整数 ai (1<=i<=n)

1<=n<=30, 2<=k<=100, 0<=ai<=10¹⁶ , 1<=T<=5

输出共 T 行：

第 i 行表示第 i 组数据的结果： 如果可以达到 a 序列，则输出 ^_^ ; 否则输出 QwQ。

3
4 100
0 0 0 0
1 2
1
3 2
0 1 3

^_^
^_^
QwQ