만드는 중입니다

아직 만드는 중이라 바뀔 수 있습니다

이진 게임

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

요약
두 사람이 이진 문자열 뒤에 0이나 1을 붙입니다. 금지된 부분문자열을 만드는 쪽이 집니다. 승자나 무승부를 구합니다.
난이도

보통10점 중 7점

유형
게임 이론, 트라이, BFS, 문자열 매칭
정답자
아직 제출이 없습니다

문제

이스칸데르와 올랴는 퍼즐을 만드는 것도 좋아하지만, 문자열 게임을 만드는 것은 더 좋아합니다. 이번에 두 사람이 떠올린 게임의 규칙은 다음과 같습니다.

  • 금지된 이진 문자열 f1,f2,…,fnf_1, f_2, \ldots, f_n의 집합을 고릅니다.
  • 시작 이진 문자열 ss를 고르되, 금지된 문자열 중 어느 것도 ss의 부분 문자열이 아니어야 합니다.
  • 플레이어들은 번갈아 가며 ss의 끝에 문자 0 또는 1을 하나씩 붙입니다. 올랴가 먼저 둡니다.
  • 자신의 차례가 끝난 뒤 금지된 문자열 중 하나라도 ss의 부분 문자열로 나타나면, 그 플레이어가 집니다.
  • 두 플레이어가 최선을 다할 때 게임이 무한히 계속될 수 있다면 무승부입니다.

입력

첫 줄에 두 정수 nn과 mm이 주어집니다 (0≤n≤1000000 \leq n \leq 100000, 0≤m≤10000000 \leq m \leq 1000000). 각각 금지된 문자열의 개수와 ss의 초기 길이입니다.

다음 nn개의 줄에는 금지된 문자열이 한 줄에 하나씩 주어집니다. 모든 문자열은 비어 있지 않으며 0과 1로만 이루어집니다. 또한 어느 것도 ss의 부분 문자열이 아닙니다. 금지된 문자열들의 길이 합은 1000000을 넘지 않습니다.

마지막 줄에는 길이 mm인 시작 문자열 ss가 주어집니다. ss는 0과 1로만 이루어집니다. ss가 빈 문자열이면 이 줄은 없으며, 줄바꿈 문자도 주어지지 않습니다.

출력

두 플레이어가 최선을 다할 때의 결과를 출력합니다.

  • 이스칸데르의 수와 상관없이 올랴가 이길 수 있으면 Olya를 출력합니다.
  • 올랴의 수와 상관없이 이스칸데르가 이길 수 있으면 Iskander를 출력합니다.
  • 최선을 다해도 게임이 계속 진행되면 Friendship을 출력합니다.

힌트

ss가 빈 문자열이면, 어느 플레이어든 매번 0을 붙이기만 해도 지지 않을 수 있습니다.

예제3

  1. 예제 1

    입력
    1 0
    1
    
    예상 출력
    Friendship
    
  2. 예제 2

    입력
    3 1
    000
    001
    011
    0
    
    예상 출력
    Olya
    
  3. 예제 3

    입력
    2 3
    1001
    000
    100
    
    예상 출력
    Iskander