A Lot of Games

1000ms

262144K

Description:

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.

Input:

The first line contains two integers, n and k (1 ≤ n ≤ 10⁵; 1 ≤ k ≤ 10⁹).

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⁵. Each string of the group consists only of lowercase English letters.

Output:

If the player who moves first wins, print "First", otherwise print "Second" (without the quotes).

Sample Input:

2 3
a
b

Sample Output:

First

Sample Input:

3 1
a
b
c

Sample Output:

First

Sample Input:

1 2
ab

Sample Output:

Second

Informação

Provedor Codeforces

Código CF455B