409928: GYM103855 K Board Game

Jeyeon and Deokin are addicted to problem-solving and they never want to retire. They developed a new board game, which they decided to not retire before they fully analyze.

The game consists of $$$K$$$ boards and $$$K$$$ pieces. The $$$i (i=1,\cdots,K)$$$th board is a grid of size $$$N_i \times M_i$$$. For each board, there are two fences that form a boundary. Fences are paths of length $$$N_i + M_i$$$ that start from the upper-left vertex and ends at the lower-right vertex, and can be traced by moving only right (R) or down (D) in steps of length 1. The two fences do not meet except at the upper-left and lower-right vertices.

For example, consider the case where $$$N_i = 5, M_i = 4$$$. In the case of (a), the two paths RRDRDDDRD, DDRRDDDRR do not meet except at the upper-left and lower-right vertices, so this can be a valid input. On the other hand, in the case of (b), the selected two fences RDRDRDRDD, DDRRDDDRR meet at a vertex other than the upper-left and lower-right vertices, so it is an invalid input. In the case of (c), one of the fences cannot be traced by moving only right and down, so it is also an invalid input.

The game starts with $$$K$$$ boards, and there are two fences on every board. Each board has a single piece that is placed on the upper left square. Jeyeon starts first, and then they alternate turns. In Jeyeon's turn, Jeyeon must select one of the $$$K$$$ pieces and move it to the square directly to the right of the current square; In Deokin's turn, Deokin must select one of the $$$K$$$ pieces and move it to the square directly below the current square; It is not allowed to move a piece across the fence. The player who is unable to make a move on their turn loses the game.

You are an avid problem solver and have a desperate desire to win. However, since Jeyeon and Deokin are very strong, you can never beat them. However, if you perfectly analyze this game, maybe they can consider retiring?

Given the $$$K$$$ boards, please determine the winner of the game if both players play optimally.

The first line contains a single integer $$$K$$$ $$$(1 \leq K)$$$.

The next $$$3K$$$ lines contains the information of the $$$i = 1, 2, \ldots, K$$$-th grids in order.

Each grid is represented by three lines. The first line contains two integers $$$N_i, M_i$$$. The next two lines contain the direction sequence of each of the fences, which is a string of length $$$N_i + M_i$$$ consisting of only R or D ($$$1 \leq N_i,\, 1 \leq M_i$$$).

The sum of $$$N_i + M_i$$$ does not exceed $$$500\ 000$$$.

Output First if Jeyeon (the first player) wins. Output Second if Deokin (the second player) wins.

2
3 2
RRDDD
DRDDR
1 2
DRR
RRD

First

2
2 2
DRDR
RRDD
4 5
RDRDDRRRD
DDDRDRRRR

Second

Illustration of sample test 1.