Нім#1097

Нім

1 секунда

64 мегабайти

Дуже легка

Давайте зіграємо у традиційну гру Нім. Ми з вами сидимо за столом, перед нами сто каменів (точна їх кількість відома). Ми ходимо по черзі; за один хід гравець може взяти від одного до чотирьох каменів із купи. Ви ходите першим. Гравець, який забирає останній камінь, програє.

У цій грі існує виграшна стратегія. Спочатку ви берете $4$ камені, залишаючи у купі $96$ . Як би я не зіграв, після мого ходу залишиться від $92$ до $95$ каменів. Потім, після вашого ходу, ви залишаєте мені $91$ камінь (переконайтеся, що це завжди можливо). Повторюючи цю процедуру, ви завжди залишаєте мені $5 k + 1$ 5k+1 каменів, і таким чином я змушений забрати останній камінь і програти. Якщо ж, натомість, спочатку було $101$ камінь, виграшна стратегія була б у мене, і ви завжди програвали б.

Узагальнимо гру. По-перше, це командна гра. У кожній команді $n$ гравців, усі $2 n$ гравців сидять за столом по черзі, так що кожен має суперників по обидва боки. Ходи йдуть по колу, команди ходять почергово. По-друге, кожен гравець має свою максимальну кількість каменів, яку він може взяти за хід (мінімум завжди один). Отже, гра стає асиметричною й можливо несправедливою.

Коли обидві команди грають оптимально, результат однозначно визначається початковою кількістю каменів і максимальним числом, яке можна взяти за хід для кожного гравця. Тобто одна з команд завжди має виграшну стратегію.

Ви — тренер команди. Перед грою суддя оголошує початкову кількість каменів і для кожного гравця максимальну кількість каменів, яку той може взяти за один хід. Ваша команда ходить першою. Визначте, чи є у вашої команди виграшна стратегія.

Вхідні дані

Кожен рядок вхідних даних описує окремий тест і, окрім останнього, містить послідовність цілих чисел у форматі:

$n S M_{1} M_{2} \dots M_{2 n}$ n\ S\ M_1\ M_2\ \ldots\ M_{2n}

де $n$ — кількість гравців у команді, $S$ — початкова кількість каменів, а $M_{i}$ M_i — максимальна кількість каменів, яку може взяти гравець $i$ за один хід. Гравці $1$ , $3$ , $5$ , ... належать вашій команді, а гравці $2$ , $4$ , $6$ , ... — команді суперників. Числа розділені пробілами. Останній рядок містить лише $0$ і не обробляється.

Вам гарантовано, що $1 \leq n \leq 10$ 1 \leq n \leq 10, $1 \leq M_{i} \leq 16$ 1 \leq M_i \leq 16, $1 \leq S < 2^{13}$ 1 \leq S < 2^{13}.

Вихідні дані

Для кожного тесту виведіть у окремому рядку $1$ , якщо у вашої команди є виграшна стратегія, інакше $0$ .

Приклади

Приклад 1