A Lot of Games

Given a trie of strings, play the prefix-building game k times with the loser starting next; report who wins the last game.

Hard8TrieGame theoryDFSDynamic programmingNo attempts yetTime limit2sMemory limit512 MB

Problem

Andrew and Alex invented a game for two players. The rules are as follows.

  • A group of n non-empty strings is given. During a game the two players build one word together. At the start the word is empty.
  • The players take turns. On their turn a player must append one lowercase letter to the end of the word, and the word after the letter is appended must be a prefix of some string in the group. If no letter can be appended under that condition, the player whose turn it is loses.
  • Neither player may resign or pass a turn. If at least one letter satisfies the condition, the player must append a letter. The game does not stop because the word became equal to a string in the group. It stops only when no letter can be appended.

Andrew and Alex have a lot of time, so they decided to repeat this game k times. The player who loses game i plays first in game i+1. They agreed that the winner of the last game is the overall winner.

Write a program that finds who wins the last game when both players play optimally.

Input

The first line contains the number of strings in the group n and the number of games k (1n1000001 \le n \le 100000, 1k1091 \le k \le 10^9).

Each of the next n lines contains one non-empty string of the group. Every string consists of lowercase letters only, and the total length of all strings is at most 100000.

Output

Print First if the player who plays first in the first game wins the last game. Print Second if the player who plays second in the first game wins the last game.