Unusual game

All submissions for this problem are available.
Read problems statements in Mandarin Chinese, Russian and Vietnamese as well.
Recently Chef invented a two player game. The game is played on a horizontal strip consisting of n cells that are numbered from left to right with consecutive integers from 1 to n. At the beginning of the game, a pawn is placed at the cell numbered x. The players make moves alternately, i.e. the first player makes all odd numbered moves (1st, 3rd, 5th and so on) and the second player all even numbered moves (2nd, 4th, 6th and so on). During the kth move the player should move the pawn either exactly k cells to the left or exactly k cells to the right (provided the pawn doesn't land outside the strip). For example, in the kth move, if the pawn is located at cell p before the move, it can be moved to either (p  k) or (p + k) if the appropriate cells are part of the strip . The player who is not able to make a move (i.e. both the above choices lead to cells outside of the strip) loses the game. Assume that both the players play optimally.
Before trying to play the game himself, Chef wants to understand the game more. So, he wants to find the outcome of m such games, where in the ith game the initial location of pawn is x_{i}. Can you please help Chef in this?
Input
The first line of the input contains an integer T denoting the number of test cases.
For each test case, the first line of input contains two space separated integers ― n and m.
The second line contains m space separated integers ― x_{1}, x_{2}, ..., x_{m}.
Output
For each test case, output a single line containing m space separated integers ― ith of them should be an integer either 1 or 2, corresponding to the player that will win if the game starts with the pawn located at cell x_{i}.
Constraints
 1 ≤ T ≤ 300
 1 ≤ the sum of n over all test cases ≤ 10^{6}
 1 ≤ m ≤ 50
 1 ≤ x_{i} ≤ n
Example
Input: 2 3 2 2 3 4 2 2 4 Output: 2 1 1 1
Explanation
Example case 1.
There are three cells in the horizontal strip.
If the pawn is initially located at cell 2, during the first move it will be moved to either 1 or 3. The second player can later move the pawn to cell 3 or 1, respectively. Now, the first player has to move the pawn to three cells to the left or to the right, both of which end up moving the pawn outside the strip, so he is unable to make a move and will lose the game in this case. Hence, the second player wins the game.
If the pawn is initially located at cell 3, the first player will have to move to cell 2 during first move and then the second player will be have no available move that can still keep the pawn on the strip, thus the second player loses the game. So, the first player is the winner in this case.
Author:  alex_2oo8 
Tester:  kingofnumbers 
Editorial  https://discuss.codechef.com/problems/UNGAME 
Tags  alex_2oo8, cook78, dynamicprogramming, fractals, math, mediumhard 
Date Added:  21012017 
Time Limit:  1 sec 
Source Limit:  50000 Bytes 
Languages:  C, CPP14, JAVA, PYTH, PYTH 3.6, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, SCM chicken, PYP3, CLOJ, FS 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions
HELP
If you are still having problems, see a sample solution here. 