Let's play a traditional game of Nim. You and I are seated at a table, with a hundred stones in front of us (the exact number of stones is known). We take turns; each turn, a player can take one to four stones from the pile. You play first. The player who takes the last stone loses.
In this game, there is a winning strategy. First, you take stones, leaving in the pile. No matter how I play, there will be between and stones left. Then, after your turn, you leave me with stones (verify this is always possible). By repeating this procedure, you always leave me with 5k+1 stones, so I am forced to take the last stone and lose. If, instead, there were stones initially, I would have a winning strategy, and you would always lose.
Let's generalize the game. First, suppose it's a team game. Each team has players; the players are seated around the table, with each player having opponents on both sides. Players take turns around the table, so the teams alternate moves. Second, let each player have their own maximum number of stones they may take per turn (the minimum is always one). Thus, the game becomes asymmetric and possibly unfair.
When both teams play optimally, the outcome is fully determined by the initial number of stones and the maximum number each player may take on their turn. Thus, one team always has a winning strategy.
You are the coach of a team. For each game, the referee announces the initial number of stones and, for each player, the maximum number of stones they may take in one turn. Your team moves first. Decide whether your team has a winning strategy.
Each input line, except for the last one, represents a test case and contains a sequence of integers in the format:
n\ S\ M_1\ M_2\ \ldots\ M_{2n}
where is the number of players per team, is the initial number of stones, and M_i is the maximum number of stones player may take. Players , , , belong to your team, and players , , , belong to the opposing team. Numbers are separated by spaces. The last line contains a single and should not be processed.
You may assume 1 \leq n \leq 10, 1 \leq M_i \leq 16, and 1 \leq S < 2^{13}.
For each test case, print a single line containing if your team has a winning strategy, and otherwise.
Example 1