x
Time limit1sMemory limit1024 MB
Given a score and a melody, color every occurrence of the melody's suffixes in the score, then decide which player wins the turn-based game on the colored notes.
- Level
Medium7 of 10
- Topics
- Game theory, String matching
- Solved
- No attempts yet
Problem
Famous composer A is looking for someone with perfect pitch to help with composing. Perfect pitch is the ability to identify the pitch of a sound by its note name without a reference sound. A person with well-developed perfect pitch can look at a score and sing the pitch exactly, which is an advantage in sight-singing.
Composer A takes a score and asks the candidate to sing a favorite melody . Composer A cares about how a melody ends, so A colors every note at the end of the melody that can be found in the score. Let the melody be . For every with , if appears as a contiguous part of the score , all notes in that occurrence are colored.
For example, take the score "1 2 3 1 2 3 1 2 1 3" and the melody "1 2 3 1". Coloring finds and colors "1 2 3 1", "2 3 1", "3 1", and "1".
- "1 2 3 1": "1 2 3 1 2 3 1 2 1 3" "1 2 3 1 2 3 1 2 1 3"
- "2 3 1": "1 2 3 1 2 3 1 2 1 3" "1 2 3 1 2 3 1 2 1 3"
- "3 1": "1 2 3 1 2 3 1 2 1 3" "1 2 3 1 2 3 1 2 1 3"
- "1": "1 2 3 1 2 3 1 2 1 3" "1 2 3 1 2 3 1 2 1 3" "1 2 3 1 2 3 1 2 1 3" "1 2 3 1 2 3 1 2 1 3"




The colored segments in total are "1 2 3 1 2 3 1 2 1 3".

Composer A uses the colored parts of the score as the test range for the sight-singing evaluation. Both candidates share this score.
The evaluation works as follows.
- At the start, every colored note is red.
- The two candidates take turns.
- A player picks a contiguous segment of the score. Every note in the segment must currently be red.
- The player sings every note in the chosen segment and recolors those notes green.
- If a player cannot pick a contiguous segment made only of red notes, that player loses.
Find the turn order that lets Sumin always win, no matter how Yewon plays. Print "First" if Sumin must pick first, or "Second" if Sumin must pick second.
Input
The first line contains the length of the score and the length of the melody , separated by a space. (; )
The second line contains the notes of the score, separated by spaces. (; )
The third line contains the notes of the melody, separated by spaces. (; )
All input values are integers.
Output
Print "First" or "Second", the turn order Sumin must choose.