Mix Mix Game

All submissions for this problem are available.
Read problems statements in Mandarin chinese , Russian and Vietnamese as well.
Vanja and Miksi really like games. After playing one game for a long time, they decided to invent another game! In this game, they have a sequence $A_1, A_2, \dots, A_N$ and two numbers $Z_1$ and $Z_2$. The rules of the game are as follows:  The players take turns alternately, starting with Vanja.  There is an integer $S$; at the beginning, $S = 0$.  In each turn, the current player must choose an arbitrary element of $A$ and either add that number to $S$ or subtract it from $S$. Each element can be selected multiple times.  Afterwards, if $S = Z_1$ or $S = Z_2$, the current player (the player who made $S$ equal to $Z_1$ or $Z_2$) is the winner of the game.  If the game lasts for $10^{10}$ turns, Vanja and Miksi decide to declare it a tie. Can you help the boys determine the winner of the game? Please note that the game can end in a tie (if nobody can make $S = Z_1$ or $S = Z_2$ in the first $10^{10}$ moves). Both players play optimally, i.e. if there is a move which guarantees the current player's victory regardless of the other player's moves, the current player will make such a move. If the current player cannot win and there is a move which guarantees that the game will end in a tie, the current player will make such a move. ### Input  The first line of the input contains a single integer $T$ denoting the number of test cases. The description of $T$ test cases follows.  The first line of each test case contains three spaceseparated integers $N$, $Z_1$ and $Z_2$.  The second line contains $N$ spaceseparated integers $A_1, A_2, \dots, A_N$. ### Output  For each test case, print a single line containing one integer — the final result of the game:  $1$ if Vanja (the first player) has a winning strategy  $2$ if Miksi (the second player) has a winning strategy  $0$ if the game ends in a tie ### Constraints  $1 \le T \le 50$  $1 \le N \le 50$  $Z_1, Z_2 \le 10^9$  $A_i \le 10^9$ for each valid $i$ ### Subtasks **Subtask #1 (25 points):** $N = 2$ **Subtask #2 (75 points):** original constraints ### Example Input ``` 3 2 6 4 4 10 1 1 1 2 2 0 7 3 4 ``` ### Example Output ``` 1 0 2 ``` ### Explanation **Example case 1:** The first player can choose the value $A_1 = 4$, subtract it from $S = 0$ and obtain $S =  (4) = 4 = Z_2$. The winner is the first player. **Example case 2:** It can be proven that neither player is able to reach $S = Z_1$ or $S = Z_2$. The result is a tie.Author:  allllekssssa 
Editorial  https://discuss.codechef.com/problems/JAGAM 
Tags  adhoc, allllekssssa, game, ltime63 
Date Added:  24082018 
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, rust, SCALA, swift, 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, kotlin, PERL6, TEXT, SCM chicken, PYP3, CLOJ, COB, 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. 