아주 많은 게임
시간 제한2초메모리 제한512 MB
문자열 집합으로 접두사를 늘려가는 게임을 k번 반복하며 매번 진 사람이 다음 게임을 시작할 때, 마지막 게임의 승자를 판정한다.
문제
Andrew와 Alex가 두 명이서 하는 게임을 만들었다. 규칙은 다음과 같다.
- 비어 있지 않은 문자열 n개로 이루어진 그룹이 주어진다. 게임이 진행되는 동안 두 플레이어는 함께 하나의 단어를 만든다. 처음에 단어는 빈 문자열이다.
- 두 플레이어는 번갈아 턴을 진행한다. 자기 턴이 된 플레이어는 단어의 끝에 알파벳 소문자 하나를 붙여야 한다. 붙인 뒤의 단어는 그룹에 있는 어떤 문자열의 접두사여야 한다. 조건에 맞게 붙일 수 있는 알파벳이 없으면 그 턴의 플레이어가 진다.
- 기권하거나 턴을 넘기는 것은 불가능하다. 조건에 맞는 알파벳이 하나라도 있으면 반드시 붙여야 한다. 만든 단어가 그룹에 있는 문자열과 같아졌다고 해서 게임이 끝나지는 않는다. 게임은 붙일 수 있는 알파벳이 없을 때만 끝난다.
Andrew와 Alex는 시간이 아주 많아서 이 게임을 k번 반복하기로 했다. i번째 게임에서 진 사람이 i+1번째 게임에서 먼저 플레이한다. 마지막 게임에서 이긴 사람을 최종 승자로 하기로 둘은 합의했다.
두 플레이어가 모두 최적으로 플레이할 때 마지막 게임에서 이기는 사람이 누구인지 구하는 프로그램을 작성하시오.
입력
첫 줄에 그룹에 포함된 문자열의 개수 n과 진행하는 게임의 수 k가 주어진다 (, ).
다음 n개의 줄에 그룹에 포함된 비어 있지 않은 문자열이 한 줄에 하나씩 주어진다. 문자열은 알파벳 소문자로만 이루어지고, 모든 문자열의 길이의 합은 100000을 넘지 않는다.
출력
첫 번째 게임에서 먼저 플레이하는 사람이 마지막 게임에서 이기면 First를 출력한다. 나중에 플레이하는 사람이 마지막 게임에서 이기면 Second를 출력한다.