Может кто-нибудь объяснить решения проблемы теории игр, перечисленные ниже

Question

Постановка задачи: Андрей, Федор и Алекс - изобретательные ребята.Теперь они изобретают игру со строками для двух игроков.

Имеется группа из n непустых строк.Во время игры два игрока строят слово вместе, изначально слово пустое.Игроки ходят по очереди.На своем шаге игрок должен добавить одну букву в конце слова, результирующее слово должно быть префиксом хотя бы одной строки из группы.Игрок проигрывает, если не может двигаться.

Андрей и Алекс решили сыграть в эту игру k раз.Игрок, проигравший в i-й игре, делает первый ход в (i + 1) -й игре.Ребята решили, что победителем всех игр является игрок, выигравший последнюю (k-ю) игру.Андрей и Алекс уже начали игру.Федор хочет знать, кто победит в игре, если оба игрока будут играть оптимально.Помогите ему.

Входные данные В первой строке содержатся два целых числа, n и k (1 ≤ n ≤ 105; 1 ≤ k ≤ 109).

Каждая из следующих n строк содержит один непустая строка из данной группы.Общая длина всех строк в группе не превышает 105. Каждая строка группы состоит только из строчных букв английского алфавита.

Выходные данные Если игрок, который двигается первым, выигрывает, выведите «First», в противном случае выведите «»Второй "(без кавычек).

Примеры:

1 2
ab

Вывод: Second

особенно я не могу понять ниже Вывод:

4 2
aaaa
bbbb
ccccc
dumbavumba

Ответ жюри: First

Answer 1

У нас есть 4 строки: "aaaa", "bbbb", "ccccc" и "dumbavumba", победитель всех игр - победитель второй игры (k = 2), а результат равен First .

Если я запускаю игру сначала , у меня есть только одно решение для выигрыша, и оно должно начинаться с буквы 'c', потому что строка "ccccc" является единственной строкой, длина которой равнанечетное число.На 5-м ходу я выиграю в первой игре.

второй игрок должен будет начать вторую (последнюю) игру с некоторыми из оставшихся строк.Все оставшиеся строки состоят из четного числа букв, что означает, что я выиграю вторую игру и буду победителем во всех играх.