Petya 和 Vasya 买了一款名为“Flip”的新卡牌游戏。游戏包含 $n$ 张双面卡牌和 $m$ 张单面卡牌:
- 双面卡牌:正面写有数字 $a_i$,背面写有数字 $b_i$。
- 单面卡牌:正面写有一个数字 $c_i$。
卡牌所有面上写的数字均不相同。初始时,所有卡牌正面朝上放置在桌面上。轮到一名玩家时,他必须执行以下两种操作之一:
- 从桌面上剩余的卡牌中移除数字最小的那张。
- 如果数字最小的卡牌是双面卡牌且正面朝上,则可以将其翻转。
移除桌面上最后一张卡牌的玩家获胜。若 Petya 先手,请确定游戏的胜者。
输入格式
第一行包含两个整数 $n$ 和 $m$ ($1 \le n, m \le 500\,000$),分别表示双面卡牌和单面卡牌的数量。
第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$ ($1 \le a_i \le 2 \cdot n + m$),表示双面卡牌正面的数字。
第三行包含 $n$ 个整数 $b_1, b_2, \dots, b_n$ ($1 \le b_i \le 2 \cdot n + m$),表示双面卡牌背面的数字。
第四行包含 $m$ 个整数 $c_1, c_2, \dots, c_m$ ($1 \le c_i \le 2 \cdot n + m$),表示单面卡牌上的数字。
保证 $1$ 到 $2 \cdot n + m$ 之间的每个数字在数组 $a, b, c$ 中恰好出现一次。
输出格式
如果 Petya 获胜,输出 "First"(不含引号);如果 Vasya 获胜,输出 "Second"(不含引号)。
样例
输入格式 1
2 1 5 3 1 2 4
输出格式 1
First
说明
在第一个样例中,初始时桌上有卡牌 3、4 和 5。为了获胜,Petya 在他的回合移除卡牌 3,随后 Vasya 必须移除卡牌 4(因为它是单面卡牌)。最后,Petya 移除卡牌 5,这意味着 Vasya 将无牌可出,Petya 获胜。
输入格式 2
1 2 2 3 4 1
输出格式 2
Second
说明
在第二个样例中,初始时桌上有卡牌 1、2 和 4。Petya 必须移除第一张卡牌,因为它是单面卡牌。然后,为了获胜,Vasya 翻转卡牌 2,此时桌上有卡牌 3 和 4。Petya 必须移除翻转后的卡牌 3,随后 Vasya 移除卡牌 4。由于卡牌被取尽,Vasya 获胜。
子任务
本题的测试点分为九个组。仅当通过某一组的所有测试点以及该组所需的所有前置组测试点时,才能获得该组的分数。请注意,某些组不需要通过样例测试。离线评测(Offline-evaluation)意味着该组的测试结果仅在比赛结束后公布。
| 组别 | 分数 | $n$ | $m$ | 所需组别 | 说明 |
|---|---|---|---|---|---|
| 0 | 0 | 样例 | |||
| 1 | 12 | $n \le 20$ | $m \le 10$ | 0 | |
| 2 | 13 | $n \le 20$ | 0, 1 | ||
| 3 | 9 | $a_i > b_i$ | |||
| 4 | 10 | $\max_{i=1}^n(a_i) < \min_{i=1}^n(b_i)$ | |||
| 5 | 6 | 区间 $[\min(a_i, b_i); \max(a_i, b_i)]$ 不相交 | |||
| 6 | 11 | $n \le 200$ | $m \le 200$ | 区间 $[\min(a_i, b_i); \max(a_i, b_i)]$ 嵌套或不相交 | |
| 7 | 14 | 5, 6 | 区间 $[\min(a_i, b_i); \max(a_i, b_i)]$ 嵌套或不相交 | ||
| 8 | 13 | $n \le 5000$ | $m \le 5000$ | 0, 1, 6 | |
| 9 | 12 | 0–8 | 离线评测 |