题目描述

两名玩家 $X$ 和 $Y$ 进行如下游戏：

• 给定一个正整数 $P$，以及一个由 $N$ 个互不相同的非负整数组成的集合 $A$：$A = \{a_1, a_2, \ldots, a_N\}$，并且每个 $a_i$ 都小于 $P$。
• 两名玩家轮流操作。每名玩家在自己的回合中从集合 $A$ 中删除一个数。
• 当恰好进行了 $K$ 步操作后，如果此时集合 $A$ 中剩余元素之和能被 $P$ 整除，则玩家 $X$ 获胜；否则玩家 $Y$ 获胜。

请编写程序 div，在双方都采用最优策略的情况下，判断谁会获胜。

输入格式

第一行包含一个正整数 $T$，表示该测试点中游戏的局数。

对于每组游戏 $i = 0, 1, \ldots, T - 1$：

• 第 $(3i + 2)$ 行包含三个整数 $N$、$K$ 和 $P$；
• 第 $(3i + 3)$ 行是字符 X 或 Y，表示哪位玩家先手；
• 第 $(3i + 4)$ 行包含 $N$ 个用空格分隔的整数 $a_1, a_2, \ldots, a_N$。

输出格式

输出一行，由 $T$ 个字符组成（中间不加分隔符），每个字符对应一组游戏。

若第 $i$ 组游戏中玩家 $X$ 无论玩家 $Y$ 如何操作都能获胜，则第 $i$ 个字符输出 X；否则输出 Y。

数据范围

• $1 \le K \le N \le 5000$
• $P \le 10^{18}$
• 对于每个 $0 \le i < N$，有 $0 \le a_i < P$
• 对于每个 $0 \le i < j < N$，有 $a_i \ne a_j$
• 在 20% 的测试点中，$N \le 25$
• 在另外 20% 的测试点中，$P$ 是一个质数

样例

输入

3
5 3 7
X
1 2 3 4 6
8 4 13
Y
5 10 6 11 2 8 9 3
6 1 12
X
1 4 5 7 9 11

输出

XYX