Under construction

Still being built. Things may change

x

Time limit1sMemory limit1024 MB

Summary
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 ss and asks the candidate to sing a favorite melody ll. 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 l_1,l_2,l_3,⋯ ,l_Ml\_1, l\_2, l\_3, \cdots , l\_M. For every xx with 1≤x≤M1 \leq x \leq M, if l_x,l_x+1,⋯ ,l_Ml\_x, l\_{x+1}, \cdots , l\_M appears as a contiguous part of the score SS, 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 NN of the score ss and the length MM of the melody ll, separated by a space. (1≤N≤1 000 0001 \leq N \leq 1\,000\,000; 1≤M≤1 000 0001 \leq M \leq 1\,000\,000)

The second line contains the notes s_is\_i of the score, separated by spaces. (1≤s_i≤201 \leq s\_i \leq 20; 1≤i≤N1 \leq i \leq N)

The third line contains the notes l_il\_i of the melody, separated by spaces. (1≤l_i≤201 \leq l\_i \leq 20; 1≤i≤M1 \leq i \leq M)

All input values are integers.

Output

Print "First" or "Second", the turn order Sumin must choose.

Examples2

  1. Example 1

    Input
    10 4
    1 2 3 1 2 3 1 2 1 3
    1 2 3 1
    
    Expected output
    First
    
  2. Example 2

    Input
    10 3
    1 2 3 1 2 3 1 2 1 3
    1 3 1
    
    Expected output
    Second