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^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

Difficulty: HARD
Tags: Graph traversal

String algorithms

Implementation

Tree algorithms

Dynamic programming

Game theory
Skill types: Dynamic programming

Starter code:

Solutions:
import math
import sys
from itertools import permutations
input = sys.stdin.readline

class Node:

	def __init__(self):
		self.children = [None] * 26
		self.isEnd = False
		self.win = False
		self.lose = False

class Trie:

	def __init__(self):
		self.root = Node()

	def insert(self, key):
		cur = self.root
		for i in range(len(key)):
			if cur.children[ord(key[i]) - ord('a')] == None:
				cur.children[ord(key[i]) - ord('a')] = Node()
			cur = cur.children[ord(key[i]) - ord('a')]
		cur.isEnd = True

	def search(self, key):
		cur = self.root
		for i in range(len(key)):
			if cur.children[ord(key[i]) - ord('a')] == None:
				return False
			cur = cur.children[ord(key[i]) - ord('a')]
		if cur != None and cur.isEnd:
			return True
		return False

	def assignWin(self, cur):
		flag = True
		for i in range(26):
			if cur.children[i] != None:
				flag = False
				self.assignWin(cur.children[i])
		if flag:
			cur.win = False
			cur.lose = True
		else:
			for i in range(26):
				if cur.children[i] != None:
					cur.win = cur.win or not cur.children[i].win
					cur.lose = cur.lose or not cur.children[i].lose

def __starting_point():
	t = Trie()
	(n, k) = list(map(int, input().split()))
	for i in range(n):
		s = input()
		if s[-1] == '\n':
			s = s[:-1]
		t.insert(s)
	t.assignWin(t.root)
	if not t.root.win:
		print('Second')
	elif t.root.lose:
		print('First')
	elif k % 2 == 1:
		print('First')
	else:
		print('Second')
__starting_point()


from sys import stdin, setrecursionlimit
setrecursionlimit(200000)
(n, k) = [int(x) for x in stdin.readline().split()]
tree = {}
for x in range(n):
	s = stdin.readline().strip()
	cur = tree
	for x in s:
		if not x in cur:
			cur[x] = {}
		cur = cur[x]

def forced(tree):
	if not tree:
		return (False, True)
	else:
		win = False
		lose = False
		for x in tree:
			(a, b) = forced(tree[x])
			if not a:
				win = True
			if not b:
				lose = True
		return (win, lose)
(a, b) = forced(tree)
if a == 0:
	print('Second')
elif a == 1 and b == 1:
	print('First')
elif k % 2 == 0:
	print('Second')
else:
	print('First')


import os
import sys
sys.setrecursionlimit(10 ** 5)
from io import BytesIO, IOBase
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')

class Trie:

	class Node:

		def __init__(self, char: str='*'):
			self.char = char
			self.children = []
			self.word_finished = False
			self.counter = 1

	def __init__(self):
		self.root = Trie.Node()

	def add(self, word: str):
		node = self.root
		for char in word:
			found_in_child = False
			for child in node.children:
				if child.char == char:
					child.counter += 1
					node = child
					found_in_child = True
					break
			if not found_in_child:
				new_node = Trie.Node(char)
				node.children.append(new_node)
				node = new_node
		node.word_finished = True

	def query(self, prefix, root=None):
		if not root:
			root = self.root
		node = root
		if not root.children:
			return 0
		for char in prefix:
			char_not_found = True
			for child in node.children:
				if child.char == char:
					char_not_found = False
					node = child
					break
			if char_not_found:
				return 0
		return node
(n, k) = map(int, input().split())
tr = Trie()
for _ in range(n):
	tr.add(input())

def can_win(node):
	if not node.children:
		return False
	for child in node.children:
		if not can_win(child):
			return True
	return False

def can_lose(node):
	if not node.children:
		return True
	for child in node.children:
		if not can_lose(child):
			return True
	return False
pos = can_win(tr.root)
pos2 = can_lose(tr.root)
if pos and pos2:
	print('First')
elif not pos:
	print('Second')
else:
	print('First' if k % 2 else 'Second')


import sys
reader = (s.rstrip() for s in sys.stdin)
input = reader.__next__

class Trie:

	def __init__(self):
		self.arr = {}

	def insert(self, word):
		for x in word:
			if x not in self.arr:
				self.arr[x] = Trie()
			self = self.arr[x]

	def dfs(self):
		if not len(self.arr):
			return (False, True)
		(win, lose) = (False, False)
		for x in self.arr:
			(w, l) = self.arr[x].dfs()
			win = win or not w
			lose = lose or not l
		return (win, lose)

def answer(flag):
	print('First' if flag else 'Second')
T = Trie()
(n, k) = list(map(int, input().split()))
for _ in range(n):
	T.insert(input())
(win, lose) = T.dfs()
if k == 1 or not win or lose or k & 1:
	answer(win)
else:
	answer(not win)


N = 100000
Z = 26
trie = [[0 for i in range(Z)] for j in range(N)]
n = 0
k = 0
nodeNum = 0

def insertNode():
	u = 0
	string = input()
	global nodeNum
	for i in range(len(string)):
		c = ord(string[i]) - ord('a')
		if trie[u][c] == 0:
			nodeNum += 1
			trie[u][c] = nodeNum
		u = trie[u][c]
stateWin = [False for i in range(N)]
stateLose = [False for i in range(N)]

def dfs(u):
	leaf = True
	for c in range(Z):
		if trie[u][c] != 0:
			leaf = False
			dfs(trie[u][c])
			stateWin[u] |= not stateWin[trie[u][c]]
			stateLose[u] |= not stateLose[trie[u][c]]
	if leaf == True:
		stateWin[u] = False
		stateLose[u] = True
(n, k) = map(int, input().split())
for i in range(n):
	insertNode()
dfs(0)
if stateWin[0] and (stateLose[0] or k % 2 == 1):
	print('First')
else:
	print('Second')


def forced(tree):
	if not tree:
		return (False, True)
	else:
		winner = False
		loser = False
		for leaf in tree:
			(a, b) = forced(tree[leaf])
			if not a:
				winner = True
			if not b:
				loser = True
		return (winner, loser)

def print_res(a, b, k):
	first = 'First'
	second = 'Second'
	if a == 1 and b == 1:
		print(first)
	elif a == 0:
		print(second)
	elif k % 2 != 0:
		print(first)
	else:
		print(second)

def main():
	(n, k) = [int(i) for i in input().split()]
	tree = {}
	for i in range(n):
		_str = input().strip()
		cur = tree
		for i in _str:
			if not i in cur:
				cur[i] = {}
			cur = cur[i]
	(a, b) = forced(tree)
	print_res(a, b, k)
main()


import os, sys
from io import BytesIO, IOBase

class Trie:

	def __init__(self, *words):
		self.root = dict()
		for word in words:
			self.add(word)

	def add(self, word):
		current_dict = self.root
		for letter in word:
			current_dict = current_dict.setdefault(letter, dict())

	def dfs(self, node):
		if not len(node):
			return 2
		out = [0, 0, 0, 0]
		for i in node:
			x = self.dfs(node[i])
			if x == 4:
				return 3
			out[x - 1] += 1
			out[3] += 1
		if out[2] == out[3]:
			return 4
		if out[0] and out[1]:
			return 3
		if out[0]:
			return 2
		return 1

def main():
	(n, k) = map(int, input().split())
	trie = Trie()
	for _ in range(n):
		trie.add(input().strip())
	z = trie.dfs(trie.root)
	if z == 1:
		print('First' if k & 1 else 'Second')
	elif z == 2:
		print('Second')
	elif z == 3:
		print('First')
	else:
		print('Second')
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
main()


from sys import stdin, setrecursionlimit
setrecursionlimit(200000)
(n, k) = [int(i) for i in stdin.readline().split()]
tree = {}
for i in range(n):
	_str = stdin.readline().strip()
	cur = tree
	for i in _str:
		if not i in cur:
			cur[i] = {}
		cur = cur[i]

def forced(tree):
	if not tree:
		return (False, True)
	else:
		winner = False
		loser = False
		for leaf in tree:
			(a, b) = forced(tree[leaf])
			if not a:
				winner = True
			if not b:
				loser = True
		return (winner, loser)
(a, b) = forced(tree)
first = 'First'
second = 'Second'
if a == 1 and b == 1:
	print(first)
elif a == 0:
	print(second)
elif k % 2 != 0:
	print(first)
else:
	print(second)


class TrieNode(object):

	def __init__(self, char: str):
		self.char = char
		self.children = []
		self.word_finished = False
		self.counter = 1

def add(root, word):
	node = root
	node.counter += 1
	for char in word:
		found_in_child = False
		for child in node.children:
			if child.char == char:
				child.counter += 1
				node = child
				found_in_child = True
				break
		if not found_in_child:
			new_node = TrieNode(char)
			node.children.append(new_node)
			node = new_node
	node.word_finished = True

def win(node):
	if node.children == []:
		return False
	for child in node.children:
		if not win(child):
			return True
	return False

def loss(node):
	if node.children == []:
		return True
	for child in node.children:
		if not loss(child):
			return True
	return False
root = TrieNode('')
(n, k) = map(int, input().split())
for j in range(n):
	add(root, input())
win = win(root)
loss = loss(root)
if not win:
	print('Second')
elif loss:
	print('First')
elif k % 2:
	print('First')
else:
	print('Second')


def main():
	(n, k) = read()
	s = set()
	for i in range(n):
		s.add(read(0))
	s = list(s)
	s.sort()
	s = treeify(s)
	res = solve(s)
	if res == 0:
		print('Second')
	if res == 1:
		print('First' if k % 2 else 'Second')
	if res == 2:
		print('Second')
	if res == 3:
		print('First')

def treeify(s):
	res = [[] for _ in range(26)]
	for i in s:
		if i:
			res[ord(i[0]) - 97].append(i[1:])
	fin = []
	for i in range(26):
		if res[i]:
			fin.append(treeify(res[i]))
	return fin

def solve(s, parity=2):
	for i in range(len(s)):
		if isinstance(s[i], list):
			s[i] = solve(s[i], 3 - parity)
	if not s:
		return parity
	if 0 in s:
		return 3
	if 1 in s and 2 in s:
		return 3
	if 1 in s:
		return 1
	if 2 in s:
		return 2
	return 0

def read(mode=2):
	inputs = input().strip()
	if mode == 0:
		return inputs
	if mode == 1:
		return inputs.split()
	if mode == 2:
		return map(int, inputs.split())

def write(s='\n'):
	if isinstance(s, list):
		s = ' '.join(map(str, s))
	s = str(s)
	print(s, end='')
main()


import collections
import time
import os
import sys
import bisect
import heapq
from typing import List

def make_trie(A):
	trie = {}
	for word in A:
		t = trie
		for w in word:
			if w not in t:
				t[w] = {}
			t = t[w]
	return trie

def game(trie):
	if not trie:
		return False
	return not all([game(t) for (k, t) in trie.items()])

def can_lose(trie):
	if not trie:
		return True
	return any([not can_lose(t) for (k, t) in trie.items()])

def solve(N, K, A):
	trie = make_trie(A)
	win = game(trie)
	if not win:
		return False
	if K == 1:
		return True
	if can_lose(trie):
		return True
	return K % 2 == 1
(N, K) = map(int, input().split())
A = []
for i in range(N):
	s = input()
	A.append(s)
print('First' if solve(N, K, A) else 'Second')