만드는 중입니다

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

왕들의 외나무다리 돌게임

시간 제한1초메모리 제한256 MB

요약
두 왕이 번갈아 자기 색 돌을 움직이는 다리 게임에서, 최적으로 둘 때 이기는 왕의 이름을 구합니다.
난이도

보통10점 중 7점

유형
게임 이론, 수학
정답자
아직 제출이 없습니다

문제

흰 왕(Whiteking)과 검은 왕(Blackking)이 외나무다리 돌게임을 하려고 합니다. 이 게임에서는 NN개의 외나무다리를 사용합니다. ii번째 외나무다리는 일렬로 놓인 AiA_i개의 칸으로 이루어져 있습니다. 모든 외나무다리의 첫 번째 칸에는 흰 돌을, 마지막 칸에는 검은 돌을 올려놓고 게임을 시작합니다.

각 턴에 왕은 자신의 색깔 돌 중 하나를 반드시 움직여야 합니다. 돌은 같은 다리의 다른 칸으로 옮겨야 합니다. 상대방의 돌을 뛰어넘을 수 없고, 같은 칸에 머무를 수도 없습니다. 이 조건을 어기지 않는 한, 돌을 양방향으로 움직일 수 있습니다. 상대 돌로부터 멀어지는 방향으로 움직이는 것도 가능합니다. 왕들은 번갈아 턴을 진행합니다. 자신의 차례에 움직일 수 있는 돌이 없는 왕이 집니다.

두 왕이 최적의 방법으로 게임을 한다면 누가 이길지 예측해 보세요.

입력

첫째 줄에 외나무다리의 개수 NN이 주어집니다.

둘째 줄에 각 외나무다리의 칸 수 A1,A2,A3,…,ANA_1, A_2, A_3, \ldots, A_N이 주어집니다.

셋째 줄에 먼저 시작하는 왕의 이름이 주어집니다.

출력

이길 왕의 이름을 출력합니다. 이름은 항상 첫 글자가 대문자입니다.

제한

  • 1≤N≤100,0001 \le N \le 100{,}000
  • 2≤Ai≤1092 \le A_i \le 10^9

힌트

칸이 6개인 외나무다리에서 흰 돌이 3번 칸에, 검은 돌이 5번 칸에 있다고 해 봅시다. 흰 돌은 1, 2, 4번 칸 중 하나로 이동할 수 있습니다. 검은 돌은 4, 6번 칸 중 하나로 이동할 수 있습니다. 돌은 상대 돌로부터 멀어지는 방향으로도 이동할 수 있다는 점에 유의하세요.

예제2

  1. 예제 1

    입력
    2
    3 3
    Whiteking
    
    예상 출력
    Blackking
    
  2. 예제 2

    입력
    2
    3 5
    Whiteking
    
    예상 출력
    Whiteking