Stone Game 7

Time limit1sMemory limit128 MB

Summary

Two players alternately remove a power of four stones from the pile, and the program reports the winner when both play perfectly.

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

Problem

The stone game is played by two people who take stones in alternating turns.

There are $N$ stones on the table. Sang-Keun and Chang-Young take turns, and on one turn a player takes exactly $4^x$ stones. Here $x$ is an integer with $x \ge 0$ , so the possible counts are 1, 4, 16, 64, and so on. The player who has no legal way to take stones on their turn loses the game.

Both players play perfectly. Write a program that finds the winner. Sang-Keun starts the game.

Input

The first line contains the number of stones $N$ . ( $1 \le N \le 1{,}000{,}000{,}000{,}000$ )

Output

Print SK if Sang-Keun wins the game, or CY if Chang-Young wins.

Examples1

Example 1
Input
```
3
```
Expected output
```
SK
```