Game theory

B. A Lot of Games

time limit per test

1 second

memory limit per test

256 megabytes

input

standard input

output

standard output

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 ≤ 105; 1 ≤ k ≤ 109).

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 105. 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

            Here we need to realise few things before getting started 

the game will be played k times. In algorithmic games we always think about the game from the perspective of the first player.   Lets see few situations

(1) If the first player can win or loose at his will then he will definitely win the kth game.

(2) If the first player never wins the second player will win all the games and hence the kth game

(3) In all cases if k is odd first will win else second will win

Now coming to solving the problem  lets first find if the first player can force a win on any ith game.

             It can only force a win if it can go to any loosing position . Which means that 

if u can jump to any loosing position u are at a winning position.  Where the leafs are loosing positions.

            lets take the example of 2 strings

           abc

           adefg

     The first player chooses a , the second chooses b or d in all cases  the first player                      wins. 

        Similarly now we need to find if the first player can loose at his will. This can be done by thinking a situation all positions i am coming from are loosing (hence and logic).

We can insert the words in a prefix trie for easy traversal. A trie is basically a directed acyclic graph if you have problem thinking about trie first think logically on a DAG and then 

go for a trie.

#include<bits/stdc++.h>
#define ff first
#define ss second 
#define pb push_back
#define mp make_pair
using namespace std;
class trie
{
 public:
         trie * hash[30];
         trie()
         {
               for(int i=0;i<26;i++)
      hash[i]=NULL; 
   }
};
void add(trie *root,string s)
{
     int l=s.length();
    // cout<<"length l "<<l<<endl;
     trie * pre=root;
     for(int i=0;i<l;i++)
     { 
            int val=s[i]-'a';
            if(pre->hash[val]==NULL)
            {
   //          cout<<"create "<<endl;
                     pre->hash[val]=new trie();
      }
  //    cout<<"go "<<endl;
      pre=pre->hash[val];
     }
}
int solve(trie * root)
{
            
    int ret=0;
    for(int i=0;i<26;i++)
    {
        if(root->hash[i]!=NULL)
        {
             ret|=solve(root->hash[i]);  
        }
    }
    return !ret;
}
int solve2(trie * root,string dd)
{
// cout<<"string  dd"<<dd<<endl;
      bool atleast=true;
      int ret=1;
       for(int i=0;i<26;i++)
       {
              if(root->hash[i]!=NULL)
              {
                atleast=false;
                string p=dd;
                p+=char(i+'0');
           ret=ret&solve2(root->hash[i],p);    
      }
    }
    if(atleast)
    {
  //      cout<<"rett 1 "<<endl;
    return 1;}
    int qq=!ret;
   // cout<<"ret "<<qq<<endl;
    return qq;
}
int main()
{
    int n;
    cin>>n;
    int k;
    cin>>k;
    string s;
    vector<string> v;
    trie * root=new trie();
    for(int i=0;i<n;i++)
    {
        cin>>s;
        v.pb(s);
    }
    for(int i=0;i<n;i++)
    {
              int l,pos;
             add(root,v[i]);
     //        cout<<"add "<<endl;
    }
    int canwin1=solve(root);    // if 1 canwin and control the game then its 0
    //   cout<<canwin1<<endl;
       int canlooseatwill=solve2(root,"");
  //  cout<<"can loose at will "<<canlooseatwill<<endl;
       if(canlooseatwill==1 && canwin1==0)
   cout<<"First"<<endl;
       else if(canwin1==1)
       {
             cout<<"Second"<<endl;
    }
       else
       {
                 if(k%2==1)
     {
       cout<<"First"<<endl;
        }       
        else cout<<"Second"<<endl;
    }
    return 0;
}