Card_Flip — OOI final
Task type: batch | Time limit: 1 s | Memory limit: 256 MB | Difficulty: 18
Algorithms: game theory, graph theory, greedy, union-find

# Card Flip

| Input file:   | standard input  |
|---------------|-----------------|
| Output file:  | 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 $a_i$, and the back side has the number $b_i$.

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

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 \le n, m \le 500000$) — the number of double-sided and single-sided cards, respectively.

The second line contains $n$ integers $a_1, a_2, ..., a_n$ ($1 \le a_i \le 2 \cdot n + m$) — the numbers written on the front side of the double-sided cards.

The third line contains $n$ integers $b_1, b_2, ..., b_n$ ($1 \le b_i \le 2 \cdot n + m$) — the numbers written on the back side of the double-sided cards.

The fourth line contains $m$ integers $c_1, c_2, ..., c_m$ ($1 \le c_i \le 2 \cdot n + m$) — the numbers written on the single-sided cards.

It is guaranteed that each number from 1 to $2 \cdot 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

| standard input         | standard output |
|------------------------|-----------------|
| 2 1<br>5 3<br>1 2<br>4 | First           |
| 1 2<br>2<br>3<br>4 1   | Second          |

## 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.

| Group | Points | Additional constraints | Required<br>Groups | Comment                                                                            |
|-------|--------|------------------------|--------------------|------------------------------------------------------------------------------------|
| 0     | 0      | –                      | –                  | Examples.                                                                          |
| 1     | 12     | $n \le 20$             | 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      | –                      | –                  | The segments [$min(a_i, b_i); max(a_i, b_i)$] do not intersect.               |
| 6     | 11     | $n \le 200,<br>m \le 200$            | –                  | The segments [$min(a_i, b_i); max(a_i, b_i)$] are nested or do not intersect. |
| 7     | 14     | –                      | 5, 6               | The segments [$min(a_i, b_i); max(a_i, b_i)$] are nested or do not intersect. |
| 8     | 13     | $n \le 5000,<br>m \le 5000$           | 0, 1, 6            |                                                                                    |
| 9     | 12     | –                      | 0 – 8              | Offline-evaluation.                                                                |

Starter code: