30754번 - Бинарная игра 다국어

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

• Выбирается какой-то набор запрещённых двоичных (состоящих из нулей и единиц) строк $f_1, f_2, \ldots, f_n$.
• Выбирается некоторая стартовая бинарная строка $s$, такая что ни одна из запрещённых строк не входит в неё как подстрока.
• Игроки по очереди дописывают в конец строки $s$ по одному символу <<0>> или <<1>>. Оля ходит первой.
• Проигрывает тот, после чьего хода хотя бы одна из запрещённых строк $f_1, f_2, \ldots f_n$ входит в $s$ как подстрока.
• В случае если при оптимальной игре обоих игроков игра может продолжаться сколь угодно долго, то объявляется ничья.

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

В первой строке входных данных записаны два целых числа $n$ и $m$ ($0 \leq n \leq 100\,000$, $0 \leq m \leq 1\,000\,000$) --- количество запрещённых строк и изначальная длина строки $s$.

В каждой из последующих $n$ строк содержится одна запрещённая строка. Гарантируется, что все эти строки непусты, состоят из символов <<0>> и <<1>> и никакая из них не является подстрокой строки $s$. Дополнительно гарантируется, что суммарная длина всех запрещённых строк не превосходит $1\,000\,000$.

В последней строке входных данных записана стартовая строка $s$ длины $m$, состоящая только из символов <<0>> и <<1>>. Обратите внимание, строка $s$ может быть пустой, в этом случае соответствующая строка входных данных отсутствует (в том числе символ перевода строки). Длина $s$ не превосходит $1\,000\,000$.

В зависимости от результата игры при оптимальной игре обоих игроков выведите:

• <<Olya>> (без кавычек), если Оля может победить вне зависимости от того как будет играть Искандер. Напомним, что Оля ходит первой.
• <<Iskander>> (без кавычек), если Искандер может победить не зависимо от ходов Оли.
• <<Friendship>> (без кавычек), если при оптимальной игре обоих игроков игра будет продолжаться бесконечно долго.

В первом примере строка $s$ изначально пустая. Любой из игроков может не проиграть на любом ходу просто приписав к $s$ символ <<0>>.