Nim

Nim is a traditional stone game. You and I sit across a table with a heap of 100 stones between us, and both of us know the exact count. We move in turn, and a move takes one to four stones off the heap. You move first, and whoever takes the last stone loses.

In this game you have a winning strategy. Take four stones first, leaving 96. Whatever I do, I hand back between 92 and 95 stones, so you can bring the heap down to 91 again (check for yourself that this is always possible). Repeating this, you always leave me $5k + 1$ stones, and the last stone ends up mine. Had the heap started at 101 stones, the winning strategy would be mine and you would lose.

Now generalize the game a little. First, make it a team game. Each team has $n$ players, and the $2n$ players sit around the table so that both neighbours of every player are opponents. Turns go around the table, so the two teams move alternately. Second, let the limit per turn differ from player to player. Player $i$ takes between 1 and $M_i$ stones on each of their turns, so the game is asymmetric and can even be unfair.

When two teams of perfect players meet, the initial number of stones and the per player limits decide the game by themselves. One of the two teams has a winning strategy.

You coach one of the teams. Before each game the umpire announces the initial number of stones and every player's limit, and your team moves first. Given those numbers, decide immediately whether your team has a winning strategy.

Rumour has it that Captain Future and the officers of Hakodate-maru love this game and play it to pass the time on missions. Wondering where they get the stones? They carry no stones, but their fuel containers hold plenty of balls.

The input is a sequence of lines. Every line except the last describes one game and has the following format.

n S M1 M2 ... M2n

$n$ is the number of players on one team, $S$ is the initial number of stones, and $M_i$ is the largest number of stones the $i$th player may take in one turn. Players 1, 3, 5, ... belong to your team, and players 2, 4, 6, ... to the opposing team. Numbers on a line are separated by a single space. The last line holds a single zero and ends the input.

$1 \le n \le 10$, $1 \le M_i \le 16$, $1 \le S \le 213$.

For each game print one line: 1 if your team has a winning strategy, 0 otherwise.