아주 많은 게임

문자열 집합으로 접두사를 늘려가는 게임을 k번 반복하며 매번 진 사람이 다음 게임을 시작할 때, 마지막 게임의 승자를 판정한다.

어려움8트라이게임 이론DFS동적 계획법아직 제출이 없습니다시간 제한2초메모리 제한512 MB

문제

Andrew와 Alex가 두 명이서 하는 게임을 만들었다. 규칙은 다음과 같다.

  • 비어 있지 않은 문자열 n개로 이루어진 그룹이 주어진다. 게임이 진행되는 동안 두 플레이어는 함께 하나의 단어를 만든다. 처음에 단어는 빈 문자열이다.
  • 두 플레이어는 번갈아 턴을 진행한다. 자기 턴이 된 플레이어는 단어의 끝에 알파벳 소문자 하나를 붙여야 한다. 붙인 뒤의 단어는 그룹에 있는 어떤 문자열의 접두사여야 한다. 조건에 맞게 붙일 수 있는 알파벳이 없으면 그 턴의 플레이어가 진다.
  • 기권하거나 턴을 넘기는 것은 불가능하다. 조건에 맞는 알파벳이 하나라도 있으면 반드시 붙여야 한다. 만든 단어가 그룹에 있는 문자열과 같아졌다고 해서 게임이 끝나지는 않는다. 게임은 붙일 수 있는 알파벳이 없을 때만 끝난다.

Andrew와 Alex는 시간이 아주 많아서 이 게임을 k번 반복하기로 했다. i번째 게임에서 진 사람이 i+1번째 게임에서 먼저 플레이한다. 마지막 게임에서 이긴 사람을 최종 승자로 하기로 둘은 합의했다.

두 플레이어가 모두 최적으로 플레이할 때 마지막 게임에서 이기는 사람이 누구인지 구하는 프로그램을 작성하시오.

입력

첫 줄에 그룹에 포함된 문자열의 개수 n과 진행하는 게임의 수 k가 주어진다 (1n1000001 \le n \le 100000, 1k1091 \le k \le 10^9).

다음 n개의 줄에 그룹에 포함된 비어 있지 않은 문자열이 한 줄에 하나씩 주어진다. 문자열은 알파벳 소문자로만 이루어지고, 모든 문자열의 길이의 합은 100000을 넘지 않는다.

출력

첫 번째 게임에서 먼저 플레이하는 사람이 마지막 게임에서 이기면 First를 출력한다. 나중에 플레이하는 사람이 마지막 게임에서 이기면 Second를 출력한다.