게임을 만들어요

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

요약

홀수 N x N 격자의 가운데에서 두 사람이 번갈아 말을 옮깁니다. 같은 칸을 다시 지나지 않으며, 테두리로 말을 먼저 옮기는 사람이 이기는 게임의 승자를 구합니다.

문제

호반우와 상호는 $N$ 이 홀수인 $N \times N$ 격자에서 게임을 한다. 격자의 가장 왼쪽 위 칸은 $(1, 1)$ 이고 가장 오른쪽 아래 칸은 $(N, N)$ 이다. 게임 규칙은 다음과 같다.

처음에 말은 격자의 정중앙 칸 $\left( \frac{N + 1}{2}, \frac{N + 1}{2} \right)$ 에 놓여 있으며, 이 칸이 시작점이다.
두 플레이어는 자신의 턴마다 말을 상하좌우 중 한 방향으로 한 칸 움직여야 한다. 한 번이라도 말이 놓였던 칸은 다시 방문할 수 없다.
자신의 턴에 말을 움직일 수 없거나, 턴이 시작할 때 말이 격자의 테두리에 있으면 그 플레이어가 진다. 격자의 테두리는 $(x, y)$ 칸에서 $x$ 또는 $y$ 가 $1$ 이나 $N$ 인 칸을 뜻한다.

호반우가 먼저 시작한다. 두 플레이어 모두 항상 최적의 방법으로 게임할 때 누가 이기는지 구하라.

첫째 줄에 양의 정수 $N$ 이 주어진다. ( $3 \leq N \leq 999$ , $N$ 은 홀수)

첫째 줄에 호반우가 이기면 Hobanwoo를, 상호가 이기면 Sangho를 출력한다.