TwoFour twofour.txt Bessie has a new two-person game named TwoFour. To play it, she has N (3 <= N <= 30) piles, each with a number of balls (0 <= nballs <= 4). The total number of balls is 2*N. The players alternate taking turns in the game; player 1 makes the first move. Each turn consists of a single valid move. A valid move consists of the following two actions: * First, the player chooses two different piles. * Second, she takes a single ball from one pile and moves it to the other pile. She can do this only if the number of balls in the second pile (including the new ball) is not greater than the number of balls remaining in the first pile after the ball is removed. The game ends when no more moves can be made. In fact, at the end of the game, every pile will contain exactly two balls. The winner of the game is the player who 'owns' most piles at the end of the game. Ties are possible. A player 'owns' a pile if the pile has two balls and this size resulted from the particular player's most recent move to or from that pile. Consider these examples: * If a player moves a ball from a pile with four balls to a pile with one ball, then she owns the second pile (with two balls). * If a player moves a ball from a pile with three balls to a pile with no balls, then she owns the first pile, now that it has two balls. * If a player moves a ball from a pile with three balls to a pile with one ball, then she owns both piles (both with two balls). Ownership can change. Consider a pile of two balls owned by one player. If the other player chooses a pile with four balls and moves a ball to the pile with two, then neither pile is owned by anyone. If, at the beginning of the game, some piles have two balls, then the piles are equally distributed among the two players with any extra pile being owned by player two. Your program must decide, for an initial game state, who will be the winner or if the game ends in a tie. Of course, the decision is based on optimal play by both players. Your program will be presented with G (1 <= G <= 1000) game states to 'solve'. PROBLEM NAME: twofour INPUT FORMAT: * Line 1: Two space-separated integers: N and G. * Lines 2..G+1: Each line contains N space-separated integers describing a game. The first integer is the number of balls in pile 1, the second integer is the number of balls in pile 2, and so on. Line 2 describes game 1, line 3 describes game 2, and so on. Your program should compute the winner for each game. SAMPLE INPUT: 5 4 0 3 4 1 2 2 2 2 2 2 1 1 2 2 4 4 3 2 1 0 OUTPUT FORMAT: * Lines 1..G: The output contains the outcome of each game. Line 1 gives the outcome of game 1, and so on. The outcome is a single integer: 1 if the first player wins, 2 if the second player wins, and 0 if the game is a tie. SAMPLE OUTPUT: 1 2 1 1