#P1290. Euclid's Game

    ID: 14577 Type: Default 1000ms 256MiB

Euclid's Game

Euclid's Game

Two descendants of Euclid, Stan and Ollie, are playing a number game invented by their ancestor Euclid. Given two positive integers \(M\) and \(N\), the game is played as follows: starting with Stan, the player selects the larger of the two numbers and subtracts a positive integer multiple of the smaller number such that the result is non-negative. Then, the turn passes to the other player, who performs the same operation on the new pair (the most recent result and the other number). The game continues until a player obtains \(0\); that player wins.

For example, with the initial pair \((25, 7)\), the game might proceed as follows:

  • Initial: \((25, 7)\)
  • Stan: \((25 - 2 \times 7, 7) = (11, 7)\)
  • Ollie: \((11, 7) \to (11, 7 - 1 \times 7) = (11, 4)\) (reordering gives \((4, 7)\))
  • Stan: \((7 - 1 \times 4, 4) = (3, 4)\) (reordering gives \((4, 3)\))
  • Ollie: \((4 - 1 \times 3, 3) = (1, 3)\)
  • Stan: \((3 - 1 \times 1, 1) = (2, 1)\); note that with optimal play Stan eventually forces a win by reaching 0.

Assuming both players play optimally, determine which player will win the game. It is known that the winning strategy can be decided by simulating the game with the following rule: Let \(a\) and \(b\) be the two numbers with \(a \ge b\). If \(\lfloor a/b \rfloor \ge 2\) or \(a \mod b = 0\), then the current player wins immediately; otherwise, the outcome is the opposite of the result when playing with \(b\) and \(a-b\).

inputFormat

The input consists of a single line containing two positive integers \(M\) and \(N\) (\(1 \leq M, N \leq 10^9\)).

outputFormat

Output a single line: either Stan wins if Stan (the first player) wins under optimal play, or Ollie wins otherwise.

sample

25 7
Stan wins