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 MBAndrew and Alex invented a game for two players. The rules are as follows.
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.
The first line contains the number of strings in the group n and the number of games k (1≤n≤100000, 1≤k≤109).
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.
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.