님 게임

전통 게임 님(Nim)을 해 보자. 너와 나는 탁자를 사이에 두고 마주 앉아 있고 탁자 위에는 돌 100개가 놓여 있다. 돌이 몇 개인지는 둘 다 정확히 안다. 두 사람은 번갈아 차례를 가지며, 자기 차례에 돌을 1개에서 4개까지 가져간다. 네가 먼저 시작하고, 마지막 돌을 가져간 사람이 진다.

이 게임에서 너에게는 필승 전략이 있다. 먼저 4개를 가져가 96개를 남겨라. 내가 어떻게 두든 92개에서 95개가 남으므로 너는 다시 91개를 남길 수 있다(항상 가능한지 직접 확인해 보라). 이렇게 두면 너는 언제나 $5k + 1$개를 내게 넘기고, 마지막 돌은 결국 내 몫이 된다. 반대로 처음에 돌이 101개였다면 필승 전략은 내게 있고 너는 진다.

이제 게임을 조금 일반화하자. 첫째, 팀 게임으로 바꾼다. 각 팀은 $n$명이고, $2n$명이 탁자에 둘러앉되 누구의 양옆에도 상대 팀 선수가 앉는다. 차례는 탁자를 따라 돌아가므로 두 팀이 번갈아 돌을 가져간다. 둘째, 한 번에 가져갈 수 있는 최대 개수를 선수마다 다르게 둔다. $i$번째 선수는 자기 차례마다 돌을 1개에서 $M_i$개까지 가져간다. 그래서 게임은 비대칭이고 불공평할 수도 있다.

두 팀이 모두 최선으로 두면 승부는 처음 돌의 개수와 선수별 최대 개수만으로 완전히 정해진다. 즉 두 팀 중 한쪽에는 반드시 필승 전략이 있다.

너는 한 팀의 감독이다. 경기마다 심판이 처음 돌의 개수와 모든 선수의 최대 개수를 알려 주고, 네 팀이 먼저 시작한다. 이 수들을 보고 네 팀에 필승 전략이 있는지 곧바로 판단하라.

참고로 캡틴 퓨처와 하코다테마루 승무원이 이 게임을 좋아해서 임무 중 짬이 날 때마다 즐긴다는 소문이 있다. 돌은 어디서 구하냐고? 돌은 없지만 연료 탱크에 공이 잔뜩 있다.

입력은 여러 줄로 이루어진다. 마지막 줄을 뺀 각 줄은 경기 하나를 나타내고 형식은 다음과 같다.

n S M1 M2 ... M2n

$n$은 한 팀의 선수 수, $S$는 처음 돌의 개수, $M_i$는 $i$번째 선수가 한 차례에 가져갈 수 있는 최대 개수다. 1번, 3번, 5번, ... 선수는 네 팀이고 2번, 4번, 6번, ... 선수는 상대 팀이다. 한 줄에서 수는 공백 하나로 구분한다. 마지막 줄에는 0 하나가 주어지고 입력이 끝난다.

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

경기마다 네 팀에 필승 전략이 있으면 1을, 없으면 0을 한 줄에 하나씩 출력한다.