The Alice and Shinobu Game

Alice and Shinobu are playing an intriguing game. Initially, there are \(n\) isolated vertices, and each vertex is colored white. The game proceeds in alternating turns with Alice starting first. The moves are as follows:

• Alice selects two distinct vertices \(u\) and \(v\) that are not connected by an edge, and adds an undirected edge \((u,v)\). Self-loops are not allowed.
• Shinobu chooses a vertex and flips its color (white turns to black and black turns to white).

The game ends immediately when, after any move, one of the following conditions occurs:

1. The graph contains a monochromatic triangle, i.e. there exist vertices \(a, b, c\) all of the same color with edges \((a,b)\), \((b,c)\), and \((c,a)\) all present.
2. The opponent has no legal move on their turn.

In either case, the player who performed the move that led to the condition wins. Assuming both players play optimally, determine which player has a winning strategy.

Note: All formulas are represented in \(\LaTeX\) format.

inputFormat

The input consists of a single integer \(n\) (with \(3 \le n \le 10^5\)) representing the number of vertices.

outputFormat

Output a single line containing either Alice or Shinobu, indicating the player who has a winning strategy.

sample

3

Shinobu