작곡가 A의 시창 평가
시간 제한1초메모리 제한1024 MB
악보와 멜로디가 주어졌을 때, 멜로디의 접미사가 악보에 나타나는 모든 위치를 색칠합니다. 그다음 두 사람이 번갈아 빨간 구간을 고르는 게임에서 먼저 시작할 사람을 구합니다.
문제
유명 작곡가 A는 자신의 작곡을 도와줄 절대음감을 가진 사람을 찾고 있다. 절대음감은 기준이 되는 다른 소리 없이 소리의 높이를 음이름으로 파악할 수 있는 능력이다. 절대음감이 발달한 사람은 악보를 보고 그 음의 높이를 그대로 낼 수 있어 시창에 유리하다. 작곡가 A는 간단한 시창 평가로, 함께 작곡할 의향을 밝힌 수민이와 예원이 중 한 명을 뽑으려 한다.
작곡가 A는 시창 평가에 쓸 악보 를 가져와, 본인이 좋아하는 멜로디 을 부르게 한다. A는 멜로디의 끝부분을 중요하게 여기므로, 악보에서 멜로디의 끝부분을 모두 찾아 음을 색칠한다. 멜로디가 일 때, 인 모든 에 대하여 이 악보 의 연속된 부분에 등장하면 해당하는 음들을 모두 색칠한다.
예를 들어 악보 “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”를 출력한다.
입력
첫째 줄에 악보 의 길이 과 멜로디 의 길이 이 공백으로 구분되어 주어진다. (; )
둘째 줄에 악보의 음 가 공백으로 구분되어 주어진다. (; )
셋째 줄에 멜로디의 음 가 공백으로 구분되어 주어진다. (; )
입력으로 주어지는 수는 모두 정수이다.
출력
수민이가 골라야 하는 순서를 “First” 또는 “Second”로 출력한다.