Codeforces Round 260 (Div. 1) |
---|

Finished |

Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

dfs and similar

dp

games

implementation

strings

trees

*1900

No tag edit access

The problem statement has recently been changed. View the changes.

×
B. A Lot of Games

time limit per test

1 secondmemory limit per test

256 megabytesinput

standard inputoutput

standard outputAndrew, 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^{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.

Output

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

Examples

Input

2 3

a

b

Output

First

Input

3 1

a

b

c

Output

First

Input

1 2

ab

Output

Second

Codeforces (c) Copyright 2010-2023 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Jun/07/2023 01:32:31 (j1).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|