本题没有可用的提交语言。

描述

国家信息学队的成员们对他们发明的新游戏感到非常自豪，他们称这个游戏为TwoFour，名字来源于他们非常喜欢的一道国际信息学奥林匹克题目。游戏的规则如下：

在这个游戏中，使用$N$个堆，每个堆中至少有$0$个珠子，最多有$4$个珠子。所有堆的珠子总数为$2 \times N$。两名玩家轮流行动，每次轮到玩家时，他必须进行一个合法的操作。

在一个合法的操作中，玩家选择两个堆，第一个堆中的珠子比第二个堆中的珠子多。玩家从第一个堆中取出一个珠子并将其移到第二个堆中。该操作只有在第二个堆中珠子数量增加后的值不超过第一个堆中剩余珠子的数量时才算合法。

当没有合法的操作时，游戏结束（如果你仔细思考一下，会发现每个堆中都将有$2$个珠子时，无法再进行合法的操作）。

游戏的获胜者是拥有更多堆的玩家。显然，如果两个玩家拥有相同数量的堆，则游戏视为平局。

玩家拥有一个堆的条件是该堆中有$2$个珠子，并且这个数量是该玩家通过自己的操作获得的。例如，如果玩家选择了一个有$4$个珠子的堆和一个有$1$个珠子的堆，经过操作后，玩家拥有第二个堆（因为它将有$2$个珠子），但是第一个堆仍然不属于任何玩家。如果玩家选择了一个有$3$个珠子的堆和一个有$0$个珠子的堆，玩家将成为第一个堆的拥有者，因为经过操作后，这个堆仍然有$2$个珠子。如果玩家选择了一个有$3$个珠子的堆和一个有$1$个珠子的堆，玩家将拥有这两个堆（因为两者都将变为$2$个珠子）。

如果某个玩家在游戏中的某一时刻拥有一个堆的$2$个珠子，这并不意味着这个堆将永远属于他。例如，假设玩家$1$拥有一个有$2$个珠子的堆，接下来轮到玩家$2$行动，如果他选择了一个有$4$个珠子的堆和玩家$1$拥有的$2$个珠子的堆，经过操作后，这两个堆的珠子数都将变为$3$，那么玩家$1$就失去了对这两个堆的控制。

如果游戏的初始配置中包含一些有$2$个珠子的堆，这些堆将均等地分配给两个玩家。如果有奇数个堆有$2$个珠子，玩家$2$将比玩家$1$多一个堆。玩家$1$是第一个行动的玩家。

编写一个程序，对于给定的$N$和初始游戏配置，判断每种游戏配置的结果。

输入

输入的第一行包含两个整数：$N$（$3 \leq N \leq 30$）和$S$（$1 \leq S \leq 1000$），表示游戏中的堆数量和初始配置的数量，接下来的每一行包含$N$个整数，这些整数属于区间$[0, 4]$，且它们的和为$2 \times N$，表示游戏的初始配置。

输出

对于每一个初始配置，按输入的顺序输出游戏的最终结果。如果玩家$1$获胜，输出$1$；如果玩家$2$获胜，输出$2$；如果是平局，输出$0$。

输入数据1

5 4
0 3 4 1 2
2 2 2 2 2
1 1 2 2 4
4 3 2 1 0

输出数据1

1
1
2
1

提示

在本示例中，程序将对每一个初始配置进行判断并输出结果。例如，在第一个配置中，经过一系列合法的操作，玩家$1$最终会获胜，因此输出$1$。

来源
Romania OI 2002