第2题：巅峰对决 (clim)

• 输入：clim.in
• 输出：clim.out
• 时间限制：1 s
• 内存限制：256 MB

题目描述

两名登山者，先手玩家和后手玩家，在一张山地地图上博弈。

地图是一个 $n$ 行 $m$ 列的网格。第 $i$ 行第 $j$ 列的格子有一个整数高度 $h_{i,j}$。地图上所有高度互不相同：没有两个格子具有相同的高度。

一个格子上放有一面旗帜。两名玩家交替移动旗帜，先手玩家先手。一名玩家的回合中：

• 该玩家必须将旗帜从当前格子移动到一个四相邻（共享一条边）且高度严格更高的格子；
• 如果当前格子不存在四相邻且高度严格更高的格子，则轮到移动的玩家无法移动并输掉游戏，另一方获胜。

由于每次移动都到一个严格更高的格子，旗帜永远不会回到它已经离开的格子，因此游戏总会在有限步之内结束。双方都采取最优策略。

给定 $q$ 个独立的询问。每个询问指定旗帜的起始格子；地图本身在询问之间不会改变。对于每个询问，判断在双方最优博弈下谁会获胜：先手玩家还是后手玩家。

输入格式

每个测试文件包含多组测试数据。第一行包含测试数据的组数 $T$（$1 \le T \le 500$）。每组测试数据的格式如下。

每组测试数据的第一行包含两个整数 $n$ 和 $m$（$1 \le n,m \le 10^5$，$n\cdot m \le 10^5$），分别表示地图的行数和列数。

接下来 $n$ 行描述高度。其中第 $i$ 行包含 $m$ 个整数 $h_{i,1},h_{i,2},\ldots,h_{i,m}$（$1 \le h_{i,j} \le 10^9$），其中 $h_{i,j}$ 为第 $i$ 行第 $j$ 列格子的高度。保证同一组测试数据内的 $n\cdot m$ 个高度互不相同。

接下来一行包含一个整数 $q$（$1 \le q \le 10^5$），表示询问数。

接下来 $q$ 行，每行包含两个整数 $r$ 和 $c$（$1 \le r \le n$，$1 \le c \le m$），表示该询问中旗帜的起始格子为第 $r$ 行第 $c$ 列。

保证同一测试文件中所有测试数据的 $n\cdot m$ 之和不超过 $10^5$，$q$ 之和不超过 $10^5$。

输出格式

对于每个询问，输出一行：如果先手玩家在最优博弈下获胜则输出 First，如果后手玩家获胜则输出 Second。

输入输出样例 #1

1
2 3
1 2 3
6 5 4
5
1 1
1 2
2 1
2 3
2 2

First
Second
Second
Second
First

说明/提示

【样例1说明】

在样例中，地图有 $2$ 行 $3$ 列。第 $1$ 行为 $1\ 2\ 3$，第 $2$ 行为 $6\ 5\ 4$，例如 $h_{2,1}=6$ 是最高的格子，$h_{1,1}=1$ 是最低的格子。

站在没有严格更高相邻格子的玩家立即输掉。

• 询问 $(2,1)$ 的高度为 $6$，是整张地图的最大值，因此先手玩家无法移动并立即输掉：答案为 Second。
• 询问 $(2,3)$ 的高度为 $4$。它唯一严格更高的相邻格子是 $(2,2)$，高度为 $5$，而 $(2,2)$ 唯一严格更高的相邻格子是 $(2,1)$，高度为 $6$。因此博弈过程是强制的：$4\to5\to6$。先手玩家移动到 $5$，后手玩家移动到 $6$，此时先手玩家无路可走并输掉。尽管 $(2,3)$ 不是最高格子，答案仍为 Second，这说明胜负不能仅凭简单的局部特征判断。
• 询问 $(1,1)$ 的高度为 $1$。先手玩家可以移动到 $(1,2)$（高度 $2$），而该位置对后手玩家而言是必败局面，因此答案为 First。

数据范围

• $1 \le T \le 500$；
• $1 \le n,m \le 10^5$；
• $\sum{n\cdot m} \le 10^5$；
• $1 \le h_{i,j} \le 10^9$；
• 同一组测试数据内的 $n\cdot m$ 个高度互不相同；
• $1 \le q \le 10^5$；
• $1 \le r \le n$，$1 \le c \le m$；
• 同一测试文件中所有测试数据的 $n\cdot m$ 之和不超过 $10^5$；
• 同一测试文件中所有测试数据的 $q$ 之和不超过 $10^5$。

部分分数据