Description
n 个人参加一场有且仅有 m 道判断题的考试。
试卷的一份答案是指一个长度为 m 的字符串,其中每个字符均为 Y 或 N,且第 i 个字符表示第 i 道题的答案。
现在已知每个人的试卷的答案,以及考试全对的人数 k1 及全错的人数 k2,试找到该场考试一个可能的正确答案,如果有多种可能,那么就输出字典序最小的那一个,如果不可能,那么输出 −1。
Input
第一行一个正整数 T,表示数据组数。
接下来 T 组数据,每组数据第一行有四个非负整数 n,m,k1,k2,接下来 n 行,每行一个长度为 m 的由 Y 或 N 构成的字符串,表示一个人的答案。
Output
对每组数据输出一行,表示所求正确答案。或者 −1。
3
2 2 2 0
YY
YY
2 2 0 0
YY
NN
2 2 1 0
YY
YY
HINT
第1,2个测试点满足:1≤n,m≤18。
第3,4个测试点满足:k1,k2 恰有一个为 0。
第5,6个测试点满足:k1+k2>0。
第7,8个测试点满足:k1=k2=0。
对于所有数据均有:1≤T≤100,1≤n,m≤50,0≤k1,k2,k1+k2≤n。