← 返回题目列表

Codeforces · 2080/C

C. 卡片翻转

中文机器翻译题面 查看原题

以下页面来自赛事官方发布的原题PDF,已完整保存并渲染到本地。

Card Flip - 原题 PDF 第 1 页
原题PDF第6页
Card Flip - 原题 PDF 第 2 页
原题PDF第7页
可复制的 PDF 提取文本
Open Olympiad in Informatics 2024/25. Second day
                                  Moscow, March 8th, 2025
Problem Glass. Card Flip

     Input file:         input.txt or standard input
    Output file:       output.txt or standard output
    Time limit:        1 second
    Memory limit:     256 megabytes

Petya and Vasya bought a new card game called ”Flip”. The game contains n double-sided cards and m
single-sided cards:

   1. Double-sided card. The front side of the card has the number ai, and the back side has the
     number bi.

   2. Single-sided card. The front side of the card has a single number ci.

All numbers written on the cards on all sides are distinct. Initially, all cards are placed on the table with
the front side up. On his turn, a player can perform exactly one of two actions:

   1. Remove from the table the card with the smallest number among the remaining cards.

   2.  If the card with the smallest number is double-sided and facing up, it can be flipped.

The player who removes the last card from the table wins. Determine the winner of the game if Petya
goes first.

Input

The first line contains two integers n and m (1 ≤n, m ≤500 000) — the number of double-sided and
single-sided cards, respectively.

The second line contains n integers a1, a2, . . ., an (1 ≤ai ≤2 · n + m) — the numbers written on the
front side of the double-sided cards.

The third line contains n integers b1, b2, . . ., bn (1 ≤bi ≤2 · n + m) — the numbers written on the back
side of the double-sided cards.

The fourth line contains m integers c1, c2, . . ., cm (1 ≤ci ≤2 · n + m) — the numbers written on the
single-sided cards.

It is guaranteed that each number from 1 to 2 · n + m appears exactly once in one of the arrays a, b, or c.

Output

Print ”First” (without quotes) if Petya wins in this game, and ”Second” (without quotes) if Vasya wins.

Examples

                  input                                   output
 2 1                                     First
 5 3
 1 2
 4

 1 2                                     Second
 2
 3
 4 1





                                         Page 6 of 11

Open Olympiad in Informatics 2024/25. Second day
                                  Moscow, March 8th, 2025

Note

In the first example, initially, the cards 3, 4, and 5 are on the table. To win, Petya discards card 3 on his
turn, after which Vasya must discard card 4, as it is single-sided. Finally, Petya discards card 5, meaning
there will be no cards left for Vasya, and Petya wins.

In the second example, initially, the cards 1, 2, and 4 are on the table. Petya must discard the first card,
as it is single-sided. Then, to win, Vasya flips card 2, so there will be cards 3 and 4 on the table. Petya
must discard the flipped card number 3, after which Vasya will discard card 4. Since the cards will run
out, Vasya will win.

Scoring

The tests for this problem consist of nine groups. Points for each group are given only if all tests of the
group and all tests of the required groups are passed. Please note that passing the example tests is not
required for some groups. Offline-evaluation means that the results of testing your solution on this
group will only be available after the end of the competition.


                          Additional constraints   Required
       Group   Points                                        Comment
                                             Groups                       n     m

           0       0        –          –          –                   Examples.

           1       12    n ≤20   m ≤10        0

           2       13    n ≤20        –            0, 1

           3       9        –          –          –                         ai > bi
           4       10        –          –          –          maxni=1(ai) < minni=1(bi)

                                                  The segments [min(ai, bi); max(ai, bi)]           5       6        –          –          –
                                                                do not intersect.

                                                  The segments [min(ai, bi); max(ai, bi)]           6       11    n ≤200  m ≤200       –
                                                                     are nested or do not intersect.

                                                  The segments [min(ai, bi); max(ai, bi)]           7       14        –          –            5, 6
                                                                     are nested or do not intersect.

           8       13    n ≤5000  m ≤5000      0, 1, 6

           9       12        –          –         0 – 8            Offline-evaluation.





                                         Page 7 of 11