은퇴한 자들의 게임

PS계를 성공적으로 은퇴한 제연이와 덕인이는 허전한 마음을 달래려고 새로운 보드게임을 만들었다. 이 게임은 $K$개의 판과 $K$개의 말로 구성된다. $i$번째 판($i=1,\cdots,K$)은 세로 길이 $N_i$, 가로 길이 $M_i$인 격자판이다. 게임을 시작하기 전에 두 사람은 각 판의 경계를 따라 울타리를 세운다.

울타리는 격자의 변을 따라 짓는다. 격자판의 왼쪽 위 꼭짓점에서 오른쪽 아래 꼭짓점까지, 한 번에 길이 1씩 오른쪽(R) 또는 아래(D)로만 움직이는 길이 $N_i + M_i$의 경로를 생각하자. 시작점과 끝점을 제외하고는 서로 만나지 않는 두 경로를 골라 그 경로를 따라 울타리를 지으면, 이를 좋은 울타리 배치라고 한다.

(a)	(b)	(c)

그림 K.1: 좋은 울타리 배치와 나쁜 울타리 배치

예를 들어 $N_i = 5$, $M_i = 4$인 경우를 보자. (a)에서는 두 경로 RRDRDDDRD와 DDRRDDDRR이 시작점과 끝점 말고는 만나지 않으므로 좋은 배치다. (b)에서는 선택한 두 경로 RDRDRDRDD와 DDRRDDDRR이 시작점과 끝점이 아닌 곳에서 만나므로 좋은 배치가 아니다. (c)에서는 한 경로가 오른쪽과 아래로만 움직이지 않으므로 역시 좋은 배치가 아니다.

게임은 각 격자판을 좋은 울타리 배치로 막은 뒤, 각 격자판의 가장 왼쪽 위 칸에 말을 하나씩 놓고 시작한다. 제연이가 먼저 하고 두 사람이 번갈아 한 턴씩 둔다. 제연이는 자기 차례에 $K$개의 말 중 하나를 골라 오른쪽으로 한 칸 옮겨야 한다. 덕인이는 자기 차례에 $K$개의 말 중 하나를 골라 아래로 한 칸 옮겨야 한다. 말은 울타리를 넘어 옮길 수 없다. 자기 차례에 움직일 말이 없는 사람이 진다.

이 게임에는 운이 전혀 개입하지 않아서, 두 사람이 최선을 다하면 게임을 하기 전에도 누가 이길지 알 수 있다. 두 사람은 더 이상 PS 문제를 풀 의지가 없으니, 누가 이기는지 알려 달라.

첫째 줄에 정수 $K$($1 \leq K$)가 주어진다. 이후 $i = 1, \cdots, K$번째 격자판의 정보가 각각 세 줄씩 주어진다. 첫째 줄에는 $N_i$와 $M_i$가 주어진다. 이어지는 두 줄에는 울타리를 짓는 두 경로가 각각 길이 $N_i + M_i$의 문자열로 주어진다. 각 문자열은 R과 D로만 이루어져 있고, 두 문자열이 함께 좋은 울타리 배치를 나타낸다. ($1 \leq N_i$, $1 \leq M_i$, $\sum_{i=1}^{K} \left(N_i+M_i\right) \leq 500\,000$)

두 사람이 최선을 다해 게임을 진행할 때 제연이가 이기면 First, 덕인이가 이기면 Second를 출력한다.

그림 K.2: 예제 1 참고

예제 1의 초기 게임판은 위와 같다. 제연이가 첫 번째 턴에 두 번째 판의 말을 오른쪽으로 움직이면 덕인이는 더 이상 말을 움직일 수 없으므로 제연이가 이긴다.