Камушки
n ямок расположены в ряд. Для каждого натурального k от 1 до n обозначим через j_k количество камешков в k-й ямке, считая ямки слева направо.
Пусть для некоторого натурального m > 1 задана возрастающая последовательность натуральных чисел l_1, l_2, …, l_m.
Двое игроков играют по следующим правилам:
за один ход можно переложить из любой ямки в соседнюю справа (порядок ямок для обоих игроков одинаков) только такое количество камешков, которое равно одному из чисел l_1, l_2, …, l_m;
проигрывает тот, кто не может сделать ход (когда во всех ямках, кроме крайней справа, количество камешков меньше чем l_1).
Входные данные
Первая строка содержит натуральные числа n и m, которые находятся в пределах от 2 до 5 включительно.
Вторая строка содержит последовательность n неотрицательных целых чисел: j_1, j_2, …, j_n.
Третья строка содержит возрастающую последовательность m натуральных чисел: l_1, l_2, …, l_m, при этом l_1 + l_2 + … + l_m < 246.
Назовем позицией этой игры расположение камешков в ямках и номер игрока, чей ход. Известно, что общее количество возможных позиций игры не превышает 1000.
Выходные данные
Напишите программу, которая в первой строке выведет номер игрока (первым ходит 1-ый игрок, затем 2-ой), который может гарантировать себе победу. Если это будет 1, то каждая из следующих строк должна содержать по n неотрицательных целых чисел, представляющих количество камешков в ямках после первого хода, который ведет к победе 1-го игрока. Необходимо представить все возможные варианты, по одной строке на каждый вариант хода, в произвольном порядке.