Description

Xiao A is a true enthusiast of turn-based games. After winning many world-class awards in turn-based games, one day he suddenly remembered a turn-based game he played in Jiangnan when he was a child.

The rules are as follows. First, a number $F$ is given. Then the game system generates $T$ game instances. Each game instance contains $N$ heaps of stones. Xiao A and his opponent take turns. On each turn, the player first chooses a positive integer $M \ge 2$ ($M$ is chosen by the player, and can differ from turn to turn, but $M$ cannot exceed the number of stones in the chosen heap). Then the player selects any heap with at least $F$ stones and splits it into $M$ heaps, such that among these $M$ heaps, the largest size is at most $1$ greater than the smallest size (i.e., as evenly as possible; in fact, under this splitting rule, once $M$ and a heap are fixed, the resulting state is determined). A player who cannot move, that is, when every heap has strictly fewer than $F$ stones, loses. Supplement: After the first player chooses one of the $N$ heaps with at least $F$ stones and splits it into $M$ heaps, there are $N + M - 1$ heaps in total. Next, Xiao A chooses one of these $N + M - 1$ heaps with at least $F$ stones, and so on.

Xiao A has always been a courteous boy, and he invites his opponent to move first. Now Xiao A wants to know, given each game instance and assuming his opponent is just as clever as he is, who will win.

Input Format

The first line contains two positive integers $T$ and $F$, denoting the number of game instances and the given number, respectively.

Each of the next $T$ lines describes one game instance. In each line, the first number $N$ is the number of initial heaps. Then follow $N$ positive integers, giving the sizes of these $N$ heaps.

Output Format

Output one line containing $T$ numbers separated by single spaces. For each game instance, output $0$ if Xiao A (the second player) will win, and $1$ if Xiao A’s opponent (the first player) will win.

4 3
1 1
1 2
1 3
1 5

0 0 1 1

Hint

For $100\%$ of the testdata, $T < 100$, $N < 100$, $F < 100000$, and each heap size $< 100000$.

All the above numbers are positive integers.

Translated by ChatGPT 5