21872번 - Deque Game

21세기 최고의 게임! 연돌이와 세순이들의 극찬을 받아낸 게임! 세계를 매혹한 게임! 바로 Deque Game입니다.

Deque Game은 두 사람이 각자 주어진 블록을 이용해 $L$층을 더 다양한 방식으로 쌓을 수 있는 사람이 승리하는 게임이다. Deque Game의 자세한 규칙은 다음과 같다.

1. 총 $K$종류의 블록이 있고, 연돌이와 세순이는 원하는 만큼 블록을 가져다 사용할 수 있다. 블록에는 $0$이상 $K$미만의 정수가 적혀있으며, 블록을 여러 개 쌓아서 스택을 만들 수 있다.
2. 게임 시작 전, 연돌이와 세순이는 각자 $N$, $M$층의 스택을 무수히 많이 받는다. 연돌이가 받는 모든 스택은 동일하다. 세순이가 받는 모든 스택도 동일하다.
3. 연돌이와 세순이는 매초 본인이 받은 스택 중 하나를 고른다. 그리고 임의의 블록을 끼워 넣는다. 스택의 가장 아래나, 가장 위, 심지어 중간에도 끼워 넣을 수 있다. 이미 $L$층이 쌓인 스택은 고르지 않는다.
4. 충분히 많은 시간이 흐르면, 더 이상 새로운 방법으로 $L$층의 스택을 만들 수 없을 것이다. 이때, 둘 중 더 많은 방식으로 $L$층의 스택을 완성한 사람이 승리한다. 만약 $L$층의 스택을 완성하는 방식의 수가 같다면 승부가 나지 않는다.

예를 들어 연돌이는 $2$층짜리 $00$스택을 무수히 많이 받고, 세순이는 $2$층짜리 $22$스택을 무수히 많이 받았다. 총 $3$종류의 블록을 이용해서 $3$층 스택을 쌓는 방법의 수는 $7$가지로 같다. 이 Deque Game은 승부가 나지 않는다.  

곧 밤 10시가 되기 때문에 마호가니 아르바이트생 선렬이는 문을 닫을 준비를 해야 한다. 하지만 이 순간에도 연돌이들과 세순이들이 Deque Game을 열심히 하고 있다. 선렬이는 매 게임판을 돌아다니며 Deque Game의 승자를 알려주기로 했다. 재빨리 Deque Game의 승자를 알려주고 게임판을 접지 않으면, 10시에 문을 닫지 못하고 벌금을 내야 할 것이다!

첫 번째 줄에 마호가니에서 연돌이와 세순이가 진행하는 Deque Game의 수 $G$가 주어진다. ($1 \leq G \leq 3\,000$)

두 번째 줄에 블록 종류의 개수를 나타내는 $K$와 쌓아야 하는 스택의 층수를 나타내는 $L$이 주어진다. ($1 \leq K \leq 10$, $1 \leq L \leq 2\,000$)

세 번째 줄부터 $G$개의 Deque Game에 대한 정보가 다음과 주어진다.

• 연돌이가 받은 스택의 크기를 나타내는 정수 $N$이 주어진다. ($1 \leq N \leq L$)
• 연돌이가 받은 스택을 나타내는 문자열 $S$가 주어진다. 문자열 $S$의 길이는 $N$이고, 스택을 나타내는 문자열은 최하단 블록부터 주어진다.
• 세순이가 받은 스택의 크기를 나타내는 정수 $M$이 주어진다. ($1 \leq M \leq L$)
• 세순이가 받은 스택을 나타내는 문자열 $T$가 주어진다. 문자열 $T$의 길이는 $M$이고, 스택을 나타내는 문자열은 최하단 블록부터 주어진다.

연돌이와 세순이가 받은 스택의 블록에는 $0$이상 $K$미만의 정수가 적혀있다.

$G$개의 줄에 Deque Game의 승자를 출력한다.

연돌이가 승리하면 Y를, 세순이가 승리하면 S를 출력한다. 만약 승부가 나지 않는다면 YS를 출력한다.