N. Nim?
time limit per test
1 second
memory limit per test
1024 megabytes
input
standard input
output
standard output

After completing a 42-kilometer run in the XXVII Campo Grande Marathon, Granza, Joãozinho, and Machado were exhausted but were celebrating their 12th-place finish for their team. This achievement marked a special moment in UDESC's history, as it was their first time receiving a medal in an ICPC (Institute of Circuit Performance Competition) competition. However, as they crossed the finish line, a new rule was announced by the event organizers: only the top-performing teams would receive medals, provided they participated in the activity organized by BRUTE (Building Runners' Universal Trading Experience), the event's sponsor.

The activity involved the youngest team member, in this case, Machado, playing a game based on the classic Nim game against an employee named Cartinha from the BRUTE company. Cartinha was instructed to play optimally. Only teams that managed to defeat Cartinha would be awarded medals. The rules were explained by BRUTE on the event day as follows:

  • The game starts with a pile containing $$$A\times B$$$ stones and is played between two players who take turns, with Machado going first;
  • Cartinha can only add or remove (if possible) any number of stones that is a multiple of $$$A\times B$$$ from the pile;
  • Machado can add or remove (if possible) any number of stones that is a multiple of either $$$A$$$ or $$$B$$$ from the pile;
  • Machado loses if, at any point, the number of stones in the pile becomes 0 or if the game extends infinitely;
  • Machado wins if, at any point, the number of stones in the pile falls between 1 and $$$K$$$ (inclusive).

Given values $$$A$$$, $$$B$$$, and $$$K$$$, determine whether Machado can secure the medal for the team or not.

Input

The input consists of a single line containing the integers $$$A$$$, $$$B$$$, and $$$K$$$ $$$(1 \le A, B, K \le 10^7)$$$.

Output

Print "S" on a single line if it's possible for Machado to win the medal, and "N" if it's not.

Examples
Input
3 2 6
Output
S
Input
6 5 20
Output
S
Input
2 2 1
Output
N
Note

In the first example, the game starts with $$$2 \cdot 3 = 6$$$ stones, and since $$$K = 6$$$, Machado wins the medal.

In the second example, the game starts with $$$30$$$ stones and Machado can remove $$$6 \cdot 2 = 12$$$ stones (leaving the pile with $$$18$$$) to secure the medal.