Нім
Давайте зіграємо у традиційну гру НІМ. Ми з Вами сидимо за столом, на якому розміщено сто камінчиків (точне число камінчиків нам відомо). Ходимо по черзі, за кожен хід дозволяється забрати з кучки до чотирьох камінчиків. Ви починаєте першим. Той, хто забирає останній камінчик – програє.
У цій грі існує виграшна стратегія. Спочатку потрібно забрати 4 каінчики, залишивши у кучці 96. Незалежно від мого ходу на столі залишиться від 92 до 95 камінчиків. Далі Ви після свого ходу залишаєте 91 (перевірте, це завжди можливо). Діючи подібним чином, Ви завжди зможете для мене залишати на столі 5k + 1 каінчиків, і тому я нажаль обов'язково заберу останній камінчик. Якби би на початку був 101 камінчик, то у меня була б виграшна стратегія, і Ви би при жовільній грі проиграли б.
Давайте трохи узагальнимо гру. По-перше, нехай гра стане командною. Кожна команда складається з n гравців, і всі 2n гравців розміщені навколо столу, біля кожного гравця з обох сторін знаходяться його супротивники. Гра йде по ходу столу, так що команди ходять по черзі. По-друге, нехай максимальна кількість камінчиків, які може взяти кожен з гравців, буде змінюватись. Тоьто кожен гравець буде знати найбільшу кількість камінчиків, яку він може взяти зі столу на кожному своєму ході (найменша кількість камінчиків, які можна взяти завжди рівна 1). Тобто гра перестає бути симетричною, і можливо, стає чесною.
Коли гравців обох команд роблять свої ходи найкращим чином, завершення гри визначається початковою кількістю камінчиків і найбільшою кількістю каінчиків, які може забирати зі столу кожен з гравців. Таким чином, одна з команд завжди має виграшну стратегію.
Ви – тренер команды. У кажній грі суддя показує командам початкову кількість камінчиків і максимальне число камінчиків, які може забирати з кучки кожен з гравців. Ваша команда ходить першою. Необхідно визначити, чи має Ваша команда виграшну стратегію.
Вхідні дані
Вхідні дані складаються з послідовності рядків. Останній рядок містить 0 і не опрацьовується. Кожен рядок, крім останнього, містить послідовність цілих чисел у наступному форматі:
n S M_1 M_2 . . . M_2n
де n – кількість гравців у команді, S – початкова кількість камінчиків, M_i – максимальна кількість камінчиків, яку може взяти i-ий гравець. 1-ий, 3-ій, 5-ий, ... гравці належать Вашій команді, а 2-ий, 4-ий, 6-ий, ... Ваші опоненти. Вхідні числа відокремлено одним пропуском. Відомо, що 1 ≤ n ≤ 10, 1 ≤ M_i ≤ 16, і 1 ≤ S < 2^13.
Вихідні дані
Для кожного тесту у окремому рядку вивести 1, якщо у Вашої команди є виграшна стратегія, і 0 якщо нема.