Бинарная игра

시간 제한2초메모리 제한1024 MB

요약

금지된 이진 문자열들과 안전한 시작 문자열이 주어질 때, 두 사람이 비트를 덧붙이며 완벽하게 둘 때 누가 이기거나 무승부가 되는지 판정한다.

난이도: 어려움10점 중 8점
유형: 문자열 매칭, 트라이, 게임 이론, 동적 계획법
정답자: 아직 제출이 없습니다

문제

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

Выбирается какой-то набор запрещённых двоичных (состоящих из нулей и единиц) строк $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>>.

예제3

예제 1
입력
```
1 0
1
```
예상 출력
```
Friendship
```
예제 2
입력
```
3 1
000
001
011
0
```
예상 출력
```
Olya
```
예제 3
입력
```
2 3
1001
000
100
```
예상 출력
```
Iskander
```