#P12079. [OOI 2025] Card Flip

[OOI 2025] Card Flip

Description

Petya 和 Vasya 买了一款新卡片游戏,名为“Flip”。游戏中有 nn 张双面卡片和 mm 张单面卡片:

  • 双面卡片:卡片正面写有数字 aia_i,背面写有数字 bib_i
  • 单面卡片:卡片正面写有数字 cic_i

所有卡片上数字均不相同。初始时,所有卡片正面朝上,放置在桌面上。在每轮回合中,玩家可以执行以下两个动作之一:

  • 从桌面上移除剩余卡片中数字最小的那一张卡片。
  • 如果数字最小的卡片是双面卡片并且正面朝上,可以将其翻转。

谁先移除桌面上的最后一张卡片,谁就获胜。Petya 先行,确定游戏的胜者。

Input Format

第一行包含两个整数 nnmm1mn5000001 \le m \le n \le 500\,000)—— 双面卡片的数量、单面卡片的数量。

第二行包含 nn 个整数 a1,a2,,ana_1, a_2, \ldots, a_n1ai2n+m1 \le a_i \le 2 \cdot n + m)—— 双面卡片正面数字的列表。

第三行包含 nn 个整数 b1,b2,,bnb_1, b_2, \ldots, b_n1bi2n+m1 \le b_i \le 2 \cdot n + m)—— 双面卡片背面数字的列表。

第四行包含 mm 个整数 c1,c2,,cmc_1, c_2, \ldots, c_m1ci2n+m1 \le c_i \le 2 \cdot n + m)—— 单面卡片正面数字的列表。

保证每个 112n+m2\cdot n + m 的数字仅在数组 aabbcc 中出现一次。

Output Format

如果 Petya 获胜,则输出 First,否则输出 Second

2 1
5 3
1 2
4
First
1 2
2
3
4 1
Second

Hint

样例解释

在第一个样例中,初始时桌面上是数字 334455。Petya 先手移除数字 33,接着 Vasya 只能移除单面牌 44,最后 Petya 再移除 55,此时卡牌全部被移除,Petya 获胜。

在第二个样例中,初始桌面为 112244。Petya 必须移除单面牌 11,然后 Vasya 可以翻转双面牌 22(反面是 33),使桌面为 3344。Petya 只能移除 33,接着 Vasya 移除 44,最终 Vasya 获胜。

评分

本题包含九个测试点分组。只有在该分组的所有测试点以及其所有依赖分组的测试点全部通过的情况下,才能获得该分组的分数。请注意,通过样例测试点对于部分分组不是必需的。Offline-evaluation 表示该分组的评测将在比赛结束后进行。

组别 分数 限制条件:nn 限制条件:mm 依赖组别 说明
0 -- 样例测试点。
1 12 n20n \le 20 m10m \le 10 0
2 13 -- 0, 1
3 9 -- -- 满足 ai>bia_i > b_i
4 10 满足 maxi=1nai<mini=1nbi\max_{i = 1}^n a_i < \min_{i = 1}^n b_i
5 6 所有区间 [min(ai,bi),max(ai,bi)][\min(a_i, b_i), \max(a_i, b_i)] 两两不相交。
6 11 n200n \le 200 m200m \le 200 所有区间 [min(ai,bi),max(ai,bi)][\min(a_i, b_i), \max(a_i, b_i)] 要么嵌套,要么不相交。
7 14 -- 5, 6
8 13 n5000n \le 5000 m5000m \le 5000 0, 1, 6
9 12 -- 0 -- 8 Offline-evaluation.