Indian National Olympiad in Informatics

Related:

Online Programming Contest, 12-13 November, 2005

IARCS home > OLYMPIAD

Advanced Division

Problem 2: A Game, (R Shreevatsa, CMI)

Consider the following game played on N × N chessboard between two players say player 1 and player 2. Initially a queen is placed at some position on the chessboard. The two players make their moves alternately, beginning with player 1. In each move a player is allowed to move the queen to the left by any number of squares or move it down by any number of squares or move it diagonally downwards to the left by any number of squares. The allowed moves are illustrated below. In the figure Q denotes the current position of the queen and the squares marked with X are the squares to which the queen may be moved in a single move.

              -----------------------
             |   |   |   |   |   |   |
              -----------------------
             |   |   |   |   |   |   |
              -----------------------
             |   |   |   |   |   |   |
              -----------------------
             | X | X | X | X | Q |   |
              -----------------------
             |   |   |   | X | X |   |
              -----------------------
             |   |   | X |   | X |   |
              -----------------------

The game ends when the queen reaches the bottom left corner of the chessboard. The player who moves the queen into this square wins the game. For example, if the game were to begin at the following configuration

              -----------------------
             |   |   |   |   |   |   |
              -----------------------
             |   |   |   |   |   |   |
              -----------------------
             |   |   |   |   |   |   |
              -----------------------
             |   | Q |   |   |   |   |
              -----------------------
             |   |   |   |   |   |   |
              -----------------------
             |   |   |   |   |   |   |
              -----------------------

then player 2 will win the game, no matter what player 1 does.

You will be given the intial position of the queen on the chessboard. Your task is to determine which player will win the game, assuming that both players are very smart and will play the best possible strategy.

Input format

The input consists of two lines. The first line contains a single integer N, describing the number of rows and columns in the chessboard. The second line contains two integers I and J describing the starting position of the queen, where I is the column number, counting from the left most column, J is the row number, counting from the top most row.

Output format

A single line with either a 1 or a 2 indicating which of the two players will win the game starting at this position.

Note: In this task, test inputs will be arranged in groups and marks will be assigned for groups of test inputs rather than to each individual test input. For example, one mark may be assigned for a group of three test inputs. This means that to score that one mark your program must run correctly on all three test inputs in the group. Thus, blindly printing 1 (or 2) is not likely to score many marks.

Test Data:

You may assume that 1 ≤ N &le 100000. You may further assume that in 40% of the inputs 1 ≤ N &le 1000. In all inputs, 1 ≤ I &le N and 1 ≤ J &le N.

Example:

Here is the sample input and output corresponding to the example discussed above.

Sample Input

6
2 4

Sample Output