Make a Game

Time limit1sMemory limit1024 MB

Summary

Players alternately extend a path that never revisits a cell, starting from the center of an odd N x N grid, and the player who moves onto the border wins. Find the winner.

Level: Medium6 of 10
Topics: Game theory, Math
Solved: No attempts yet

Problem

Hobanwoo and Sangho play a game on an $N \times N$ grid, where $N$ is odd. The top-left cell is $(1, 1)$ and the bottom-right cell is $(N, N)$ . The rules are as follows.

At the start, a piece sits on the center cell $\left( \frac{N + 1}{2}, \frac{N + 1}{2} \right)$ , which is the starting point.
On their turn, each player must move the piece one cell up, down, left, or right. A cell that the piece has occupied at any earlier point cannot be visited again.
A player loses if they cannot move on their turn, or if the piece is on the border of the grid when their turn starts. A border cell is a cell $(x, y)$ where $x$ or $y$ is $1$ or $N$ .

Hobanwoo moves first. If both players always play optimally, determine who wins.

Input

The first line contains an odd integer $N$ . ( $3 \leq N \leq 999$ )

Output

Print Hobanwoo if Hobanwoo wins, or Sangho if Sangho wins.

Examples2

Example 1
Input
```
3
```
Expected output
```
Hobanwoo
```
Example 2
Input
```
5
```
Expected output
```
Sangho
```