이진 게임
시간 제한2초메모리 제한1024 MB
두 사람이 이진 문자열 뒤에 0이나 1을 붙입니다. 금지된 부분문자열을 만드는 쪽이 집니다. 승자나 무승부를 구합니다.
문제
이스칸데르와 올랴는 퍼즐을 만드는 것도 좋아하지만, 문자열 게임을 만드는 것은 더 좋아합니다. 이번에 두 사람이 떠올린 게임의 규칙은 다음과 같습니다.
- 금지된 이진 문자열 의 집합을 고릅니다.
- 시작 이진 문자열 를 고르되, 금지된 문자열 중 어느 것도 의 부분 문자열이 아니어야 합니다.
- 플레이어들은 번갈아 가며 의 끝에 문자 0 또는 1을 하나씩 붙입니다. 올랴가 먼저 둡니다.
- 자신의 차례가 끝난 뒤 금지된 문자열 중 하나라도 의 부분 문자열로 나타나면, 그 플레이어가 집니다.
- 두 플레이어가 최선을 다할 때 게임이 무한히 계속될 수 있다면 무승부입니다.
입력
첫 줄에 두 정수 과 이 주어집니다 (, ). 각각 금지된 문자열의 개수와 의 초기 길이입니다.
다음 개의 줄에는 금지된 문자열이 한 줄에 하나씩 주어집니다. 모든 문자열은 비어 있지 않으며 0과 1로만 이루어집니다. 또한 어느 것도 의 부분 문자열이 아닙니다. 금지된 문자열들의 길이 합은 1000000을 넘지 않습니다.
마지막 줄에는 길이 인 시작 문자열 가 주어집니다. 는 0과 1로만 이루어집니다. 가 빈 문자열이면 이 줄은 없으며, 줄바꿈 문자도 주어지지 않습니다.
출력
두 플레이어가 최선을 다할 때의 결과를 출력합니다.
- 이스칸데르의 수와 상관없이 올랴가 이길 수 있으면 Olya를 출력합니다.
- 올랴의 수와 상관없이 이스칸데르가 이길 수 있으면 Iskander를 출력합니다.
- 최선을 다해도 게임이 계속 진행되면 Friendship을 출력합니다.
힌트
가 빈 문자열이면, 어느 플레이어든 매번 0을 붙이기만 해도 지지 않을 수 있습니다.