Камінці#7202

Камінці

1 секунда

64 мегабайти

Середня

$n$ ямок розташовано у ряд. Для натурального $k$ у межах від $1$ до $n$ через $j_{k}$ j_k позначимо кількість камінців у $k$ -ій ямці, якщо рахувати ямки зліва направо.

Нехай при деякому натуральному $m > 1$ m > 1 послідовність натуральних чисел $l_{1}$ l_1, $l_{2}$ l_2, …, $l_{m}$ l_m зростає.

Двоє гравців грають таким чином:

за один хід дозволяється перекласти з будь-якої ямки у сусідню праворуч (порядок розташування ямок для обох гравців однаковий) лише таку кількість камінців, що дорівнює одному з чисел $l_{1}$ l_1, $l_{2}$ l_2, …, $l_{m}$ l_m;
програє той, хто не може зробити хід (коли в усіх ямках, крім крайньої праворуч, кількість камінців менша за $l_{1}$ l_1).

Вхідні дані

Перший рядок містить натуральні числа $n$ та $m$ , які лежать в межах від $2$ до $5$ включно.

Другий рядок містить послідовність $n$ невід'ємних цілих чисел: $j_{1}$ j_1, $j_{2}$ j_2, …, $j_{n}$ j_n.

Третій рядок містить послідовність $m$ натуральних чисел: $l_{1}$ l_1, $l_{2}$ l_2, …, $l_{m}$ l_m, що зростає, причому $l_{1} + l_{2} + \dots + l_{m} < 246$ l_1 + l_2 + … + l_m < 246.

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

Вихідні дані

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

Приклади

Приклад 1