시간 제한메모리 제한제출정답맞은 사람정답 비율
1 초 (추가 시간 없음) 1024 MB (추가 메모리 없음)60191869.231%

문제

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를 출력한다.

예제 입력 1

2
3 2
RRDDD
DRDDR
1 2
DRR
RRD

예제 출력 1

First

예제 입력 2

2
2 2
DRDR
RRDD
4 5
RDRDDRRRD
DDDRDRRRR

예제 출력 2

Second

노트

그림 K.2: 예제 1 참고

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