#P3024. Cow Checkers

    ID: 16282 Type: Default 1000ms 256MiB

Cow Checkers

Cow Checkers

Bessie has challenged Farmer John to a game of Cow Checkers, played on an (M \times N) checkerboard. The board uses coordinates such that the bottom-left square is ((0, 0)) and the top-right square is ((M-1, N-1)). Initially, a single checker starts at position ((x, y)) with (0 \le x < M) and (0 \le y < N).

Players alternately move the checker with Bessie making the first move. In each turn, a player may make one of the following moves (provided the move keeps the checker on the board):

  1. Move the checker to any square on the same row to the left of its current position.
  2. Move the checker to any square on the same column below its current position.
  3. Move the checker diagonally: that is, move (k) squares to the left and (k) squares down concurrently, for any positive integer (k) such that the new position remains on the board.

The game ends when the current player is unable to make a move (i.e. when the checker is at ((0,0))). That player loses. Given the game is played for (T) rounds with a new starting position ((x,y)) provided for each round, determine the winner of each game assuming both players play optimally.

It can be shown that this game is equivalent to Wythoff Nim. In Wythoff Nim, a position ((x,y)) (assuming without loss of generality that (x \le y)) is a losing position if and only if (x = \lfloor (y - x)\phi \rfloor), where (\phi = \frac{1+\sqrt{5}}{2}) is the golden ratio. In such cases, the player whose turn it is (Bessie, if it is the first move) cannot force a win.

inputFormat

The first line of input contains three integers (M), (N) and (T) (the dimensions of the board and the number of games) separated by spaces. Each of the following (T) lines contains two integers (x) and (y) representing the starting position of the checker piece in that game.

outputFormat

For each game, output the winner's name on a new line: output either Bessie if she can force a win or Farmer John if she cannot.

sample

5 5 3
0 0
1 2
2 2
Farmer John

Farmer John Bessie

</p>