#P16298. [Ucpc2021]Board Game

[Ucpc2021]Board Game

题目描述

游戏由 KK 个棋盘和 KK 枚棋子组成。第 ii 个棋盘是一个 Ni×MiN_i\times M_i 的网格。

对每个棋盘,沿网格边从左上角顶点走到右下角顶点,每一步只能向右 R 或向下 D。选取两条长度为 Ni+MiN_i+M_i 的这样的路径作为围栏。除起点和终点外,两条路径不得相交;满足条件的围栏称为合法围栏布局

下图中,(a) 合法,(b) 的两条路径在中间相交,(c) 中有路径并非只向右或向下,因此后两者均不合法。

游戏开始时,每个棋盘的左上角单元格各放置一枚棋子。先手 Jeyeon 与后手 Deokin 轮流操作:

  • Jeyeon 的回合:选择任意一枚棋子,将其向右移动一格;
  • Deokin 的回合:选择任意一枚棋子,将其向下移动一格。

棋子不能跨越围栏。无法进行合法移动的玩家输掉游戏。

给定所有棋盘的围栏布局,判断双方均采用最优策略时谁会获胜。

输入格式

第一行包含整数 KK

随后依次给出 KK 个棋盘。每个棋盘用三行描述:

  1. 第一行包含两个整数 Ni,MiN_i,M_i
  2. 第二、三行各包含一个长度为 Ni+MiN_i+M_i、仅由 RD 组成的字符串,表示两条围栏路径。

输入保证每一对路径构成合法围栏布局。

数据范围:

K1,Ni1,Mi1,K\ge 1,\qquad N_i\ge 1,\qquad M_i\ge 1, i=1K(Ni+Mi)500000.\sum_{i=1}^{K}(N_i+M_i)\le 500000.

输出格式

若先手 Jeyeon 获胜,输出:

First

否则输出:

Second

样例 1

输入

2
3 2
RRDDD
DRDDR
1 2
DRR
RRD

输出

First

样例 1 的初始棋盘如下:

样例 2

输入

2
2 2
DRDR
RRDD
4 5
RDRDDRRRD
DDDRDRRRR

输出

Second