32299번 - 게임을 만들어요

문제

호반우와 상호는 $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를 출력한다.

제한

노트