12884번 - A Lot of Games

Andrew와 Alex는 두 명이 할 수 있는 새로운 게임을 만들었다. 게임의 내용은 다음과 같다.

• n개의 비어있지 않은 문자열으로 이루어진 그룹이 주어진다. 게임이 진행되는 동안, 두 명의 플레이어는 함께 하나의 단어를 만든다. 처음에 단어는 빈 문자열 상태이다.
• 각 플레이어는 번갈아 턴을 수행한다. 각 턴에, 플레이어는 단어의 끝에 하나의 알파벳을 붙여야 한다. 이때, 알파벳을 붙인 후의 단어는 그룹 내의 어떤 문자열의 접두사이여야 한다. 만약 더 이상 붙일 수 있는 알파벳이 없는 경우, 그 플레이어가 패배하게 된다.
• 두 플레이어 모두 기권하거나 턴을 넘기는 것은 불가능하다. 즉, 뒤에 붙일 수 있는 (조건에 맞는) 알파벳이 존재한다면, 반드시 알파벳을 붙여야 한다.

Andrew와 Alex는 아주 시간이 많기 때문에, 이 게임을 k번 반복하기로 했다. i번째 게임에서 패배한 사람이 다음 게임에서 먼저 플레이하게 된다. 둘은 마지막 게임에서 승리한 사람이 최종 승자가 되는 것으로 합의하였다.

두 명의 플레이어가 모두 최적의 방법으로 플레이할 때, 마지막 게임에서 승리하는 사람이 누가 될지를 구하는 프로그램을 작성하시오.

첫 번째 줄에는 그룹에 포함된 문자열의 개수 n, 플레이하는 게임의 수 k가 주어진다 (1 ≤ n ≤ 100,000; 1 ≤ k ≤ 10⁹)

다음 n개의 줄에는 그룹에 포함된 비어있지 않은 문자열들이 주어진다. 모든 문자열의 길이의 합은 100,000을 넘지 않으며, 문자열에는 알파벳 소문자만이 사용된다.

첫 번째 게임에서 처음으로 플레이하는 사람이 승리할 경우 “First”를 출력한다. 나중에 플레이하는 사람이 승리할 경우 “Second”를 출력한다.