만드는 중입니다

아직 만드는 중이라 바뀔 수 있습니다

작곡가 A의 시창 평가

시간 제한1초메모리 제한1024 MB

요약
악보와 멜로디가 주어졌을 때, 멜로디의 접미사가 악보에 나타나는 모든 위치를 색칠합니다. 그다음 두 사람이 번갈아 빨간 구간을 고르는 게임에서 먼저 시작할 사람을 구합니다.
난이도

보통10점 중 7점

유형
게임 이론, 문자열 매칭
정답자
아직 제출이 없습니다

문제

유명 작곡가 A는 자신의 작곡을 도와줄 절대음감을 가진 사람을 찾고 있다. 절대음감은 기준이 되는 다른 소리 없이 소리의 높이를 음이름으로 파악할 수 있는 능력이다. 절대음감이 발달한 사람은 악보를 보고 그 음의 높이를 그대로 낼 수 있어 시창에 유리하다. 작곡가 A는 간단한 시창 평가로, 함께 작곡할 의향을 밝힌 수민이와 예원이 중 한 명을 뽑으려 한다.

작곡가 A는 시창 평가에 쓸 악보 ss를 가져와, 본인이 좋아하는 멜로디 ll을 부르게 한다. A는 멜로디의 끝부분을 중요하게 여기므로, 악보에서 멜로디의 끝부분을 모두 찾아 음을 색칠한다. 멜로디가 l_1,l_2,l_3,⋯ ,l_Ml\_1, l\_2, l\_3, \cdots , l\_M일 때, 1≤x≤M1 \leq x \leq M인 모든 xx에 대하여 l_x,l_x+1,⋯ ,l_Ml\_x, l\_{x+1}, \cdots , l\_M이 악보 SS의 연속된 부분에 등장하면 해당하는 음들을 모두 색칠한다.

예를 들어 악보 “1 2 3 1 2 3 1 2 1 3”에서 멜로디 “1 2 3 1”로 색칠하면 “1 2 3 1”, “2 3 1”, “3 1”, “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”

색칠된 구간을 모두 합치면 “1 2 3 1 2 3 1 2 1 3”이 된다.

작곡가 A는 악보에서 색칠된 부분을 시창 평가의 시험 범위로 정했다. 이 악보는 두 참가자 모두에게 공유된다.

평가 방식은 다음과 같다.

  • 처음에 색칠된 부분은 모두 빨간색이다.
  • 두 참가자는 번갈아 진행한다.
  • 악보에서 연속된 구간을 고른다. 선택한 구간의 음들은 모두 빨간색이어야 한다.
  • 고른 구간의 모든 음을 부르고, 부른 음들을 초록색으로 다시 칠한다.
  • 빨간색으로 칠해진 연속된 구간을 고를 수 없으면 그 사람은 탈락한다.

예원이가 어떻게 고르든 수민이가 항상 이길 수 있는 순서를 찾아보자. 수민이가 먼저 골라야 하면 “First”, 두 번째로 골라야 하면 “Second”를 출력한다.

입력

첫째 줄에 악보 ss의 길이 NN과 멜로디 ll의 길이 MM이 공백으로 구분되어 주어진다. (1≤N≤1 000 0001 \leq N \leq 1\,000\,000; 1≤M≤1 000 0001 \leq M \leq 1\,000\,000)

둘째 줄에 악보의 음 s_is\_i가 공백으로 구분되어 주어진다. (1≤s_i≤201 \leq s\_i \leq 20; 1≤i≤N1 \leq i \leq N)

셋째 줄에 멜로디의 음 l_il\_i가 공백으로 구분되어 주어진다. (1≤l_i≤201 \leq l\_i \leq 20; 1≤i≤M1 \leq i \leq M)

입력으로 주어지는 수는 모두 정수이다.

출력

수민이가 골라야 하는 순서를 “First” 또는 “Second”로 출력한다.

예제2

  1. 예제 1

    입력
    10 4
    1 2 3 1 2 3 1 2 1 3
    1 2 3 1
    
    예상 출력
    First
    
  2. 예제 2

    입력
    10 3
    1 2 3 1 2 3 1 2 1 3
    1 3 1
    
    예상 출력
    Second