왕들의 외나무다리 돌게임
시간 제한1초메모리 제한256 MB
두 왕이 번갈아 자기 색 돌을 움직이는 다리 게임에서, 최적으로 둘 때 이기는 왕의 이름을 구합니다.
문제
흰 왕(Whiteking)과 검은 왕(Blackking)이 외나무다리 돌게임을 하려고 합니다. 이 게임에서는 개의 외나무다리를 사용합니다. 번째 외나무다리는 일렬로 놓인 개의 칸으로 이루어져 있습니다. 모든 외나무다리의 첫 번째 칸에는 흰 돌을, 마지막 칸에는 검은 돌을 올려놓고 게임을 시작합니다.
각 턴에 왕은 자신의 색깔 돌 중 하나를 반드시 움직여야 합니다. 돌은 같은 다리의 다른 칸으로 옮겨야 합니다. 상대방의 돌을 뛰어넘을 수 없고, 같은 칸에 머무를 수도 없습니다. 이 조건을 어기지 않는 한, 돌을 양방향으로 움직일 수 있습니다. 상대 돌로부터 멀어지는 방향으로 움직이는 것도 가능합니다. 왕들은 번갈아 턴을 진행합니다. 자신의 차례에 움직일 수 있는 돌이 없는 왕이 집니다.
두 왕이 최적의 방법으로 게임을 한다면 누가 이길지 예측해 보세요.
입력
첫째 줄에 외나무다리의 개수 이 주어집니다.
둘째 줄에 각 외나무다리의 칸 수 이 주어집니다.
셋째 줄에 먼저 시작하는 왕의 이름이 주어집니다.
출력
이길 왕의 이름을 출력합니다. 이름은 항상 첫 글자가 대문자입니다.
제한
힌트
칸이 6개인 외나무다리에서 흰 돌이 3번 칸에, 검은 돌이 5번 칸에 있다고 해 봅시다. 흰 돌은 1, 2, 4번 칸 중 하나로 이동할 수 있습니다. 검은 돌은 4, 6번 칸 중 하나로 이동할 수 있습니다. 돌은 상대 돌로부터 멀어지는 방향으로도 이동할 수 있다는 점에 유의하세요.