S-Nim

Arthur and his sister Caroll have been playing a game called Nim for some time now. Nim is played as follows:

- The starting position has a number of heaps, all containing some, not necessarily equal, number of beads. - The players take turns choosing a heap and removing a positive number of beads from it. - The first player unable to make a move loses.

Arthur and Caroll really enjoyed playing this simple game, until they recently learned an easy way to always find the best move:

- Xor the number of beads in the heaps in the current position (for example, if the heaps have $2$, $4$, and $7$ beads, the xor-sum is 2 \mathbin{\mathrm{xor}} 4 \mathbin{\mathrm{xor}} 7 = 1). - If the xor-sum is $0$, then you will lose. - Otherwise, make a move so that the xor-sum becomes $0$. This is always possible.

It is quite easy to convince yourself that this works. Consider these facts:

- The player who takes the last bead wins. - After the winning player's last move, the xor-sum is $0$. - The xor-sum changes with every move.

So, if you ensure the xor-sum is $0$ after your move, your opponent will never be able to win, and thus, you will win. Understandably, the game is no fun when both players know how to play perfectly. Fortunately, Arthur and Caroll soon came up with a similar game, S-Nim. In this game, each player is only allowed to remove a number of beads that is present in the set $S$. For example, if S = \{2, 5\}, each player is only allowed to remove either $2$ or $5$ beads from any heap. Now it is not always possible to make the xor-sum $0$ with your move, so the previous strategy does not always work.

Your job is to determine whether a given position in S-Nim is a winning or losing position. A position is called winning if there is at least one move to a losing position. A position is losing if there are no moves to a losing position. If no moves are possible from a position, it is considered losing.