은퇴한 자들의 게임

PS계를 성공적으로 은퇴한 제연이와 덕인이는 허전한 마음을 달래기 위해 새로운 보드게임을 개발했다. 이 게임은 $K$개의 판과 $K$개의 말로 구성된다. $i (i=1,\cdots,K)$번째 판은 세로 길이 $N\_i$, 가로 길이 $M\_i$ 크기의 격자판인데, 게임을 시작하기 전 울타리를 사용해 경계를 만든다.

울타리는 격자의 변을 따라 짓는다. 격자판의 왼쪽 위 꼭짓점에서부터 오른쪽(R) 또는 아래(D)로만 길이 1씩 움직여서 오른쪽 아래 꼭짓점에 도달하는 길이 $N\_i + M\_i$의 경로들을 고려하자. 이 중 시작점과 끝점을 제외하고는 만나지 않는 두 경로를 골라 이들을 따라 울타리를 지었을 때 이를 좋은 울타리 배치라고 한다.

(a)	(b)	(c)

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

예를 들어 $N\_i = 5, M\_i = 4$인 경우를 살펴보자. (a)의 경우 두 경로 RRDRDDDRD, DDRRDDDRR이 시작점과 끝점을 제외하고는 만나지 않으므로 좋은 울타리 배치이다. 한편 (b)의 경우 선택된 두 경로 RDRDRDRDD, DDRRDDDRR이 시작점도 끝점도 아닌 곳에서 만나므로 좋은 울타리 배치가 아니다. (c)의 경우 두 경로 중 하나가 오른쪽 또는 아래로만 움직이는 경로가 아니므로 마찬가지로 좋은 울타리 배치가 아니다.

게임은 $K$개의 격자판에 각각 좋은 울타리 배치로 경계를 만든 뒤, 각 격자판의 가장 왼쪽 위 칸에 말을 하나씩 놓은 상태로 시작된다. 게임은 제연이가 먼저 시작해 한 턴씩 번갈아 가며 진행된다. 제연이는 자신의 차례에 $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의 초기 게임판은 위와 같다. 제연이가 첫 번째 턴에 두 번째 판의 말을 오른쪽으로 움직이면 덕인이는 더 이상 말을 움직일 수 없으므로 제연이가 이긴다.