302362: CF455B. A Lot of Games
Memory Limit:256 MB
Time Limit:1 S
Judge Style:Text Compare
Creator:
Submit:0
Solved:0
Description
A Lot of Games
题意翻译
Andrew,Fedor和Alex是三个善于创造的人。现在,他们发明了一种字符串双人游戏。 给出n个非空字符串。在游戏中,两位玩家一起建造一个单词。开始时,单词是一个空字符串。两位玩家轮流操作。一位玩家在他的回合中,必须在单词的后面添加一个字母,使得添加后的单词是n个字符串中至少一个的前缀。当一位玩家不能操作时,他就输掉了游戏。 Andrew和Alex决定玩k次。上一局的负者是下一局的先手。他们决定,在最后一局中获胜的人获得整场游戏的胜利。Andrew和Alex已经开始玩了,Fedor想知道,如果他们两个足够聪明,谁会胜利。题目描述
Andrew, Fedor and Alex are inventive guys. Now they invent the game with strings for two players. Given a group of $ n $ non-empty strings. During the game two players build the word together, initially the word is empty. The players move in turns. On his step player must add a single letter in the end of the word, the resulting word must be prefix of at least one string from the group. A player loses if he cannot move. Andrew and Alex decided to play this game $ k $ times. The player who is the loser of the $ i $ -th game makes the first move in the $ (i+1) $ -th game. Guys decided that the winner of all games is the player who wins the last ( $ k $ -th) game. Andrew and Alex already started the game. Fedor wants to know who wins the game if both players will play optimally. Help him.输入输出格式
输入格式
The first line contains two integers, $ n $ and $ k $ ( $ 1<=n<=10^{5} $ ; $ 1<=k<=10^{9} $ ). Each of the next $ n $ lines contains a single non-empty string from the given group. The total length of all strings from the group doesn't exceed $ 10^{5} $ . Each string of the group consists only of lowercase English letters.
输出格式
If the player who moves first wins, print "First", otherwise print "Second" (without the quotes).
输入输出样例
输入样例 #1
2 3
a
b
输出样例 #1
First
输入样例 #2
3 1
a
b
c
输出样例 #2
First
输入样例 #3
1 2
ab
输出样例 #3
Second