Недавно Люба купила себе набор домино, состоящий из n доминошек. Открыв набор, она сильно удивилась, потому что доминошки были необычными. Доминошка — это прямоугольник размера 1 × 2. В этом наборе есть только 3 типа доминошек:
- полностью белые (оба квадрата покрашены в белый цвет);
- полностью чёрные (оба квадрата покрашены в чёрный цвет);
- чёрно-белые (один из квадратов покрашен в белый цвет, а другой — в чёрный).
В прилагаемых к набору правилах было сказано, что играть в них должен только один человек и его главная задача — положить эти доминошки в горизонтальный ряд длины 2·n так, чтобы в получившемся ряду было ровно k отрезков чёрного цвета. Любую чёрно-белую доминошку можно развернуть на 180 градусов при помещении в ряд.
Отрезком черного цвета называется такой набор подряд идущих квадратов, каждый из которых имеет черный цвет, а слева и справа набор ограничен белыми квадратами или границами ряда.
На представленном рисунке выложено 5 доминошек, и они образуют 3 отрезка чёрного цвета Люба, конечно же, хочет выиграть, но так как доминошек могло быть очень много, она обратилась за помощью к вам! Напишите программу, которая составляет из всех имеющихся доминошек горизонтальный ряд, в котором есть ровно k отрезков чёрного цвета, либо сообщите, что с данным набором домино выиграть нельзя. Каждая доминошка из набора должна быть выложена ровно один раз.
В первой строке следуют четыре целых числа k, n1, n2 и n3 (0 ≤ k ≤ 3·105, 0 ≤ n1, n2, n3 ≤ 105, n1 + n2 + n3 > 0) — требуемое количество отрезков черного цвета, количество доминошек первого, второго и третьего типа, соответственно.
Выведите «Impossible» (без кавычек), если с данным набором выиграть нельзя.
В противном случае, выведите строку длины 2·n, соответствующую искомому ряду из n доминошек. Первый и второй символ должны соответствовать первой выложенной доминошке, третий и четвёртый — второй выложенной доминошке, и так далее. Соответственно, (2·n - 1)-й и (2·n)-й символы должны соответствовать n-й выложенной доминошке. При этом, если i-й символ выведенной строки
- равен 0, то квадрат на позиции i в ряде имеет белый цвет;
- равен 1, то квадрат на позиции i в ряде имеет черный цвет.
Каждая доминошка из набора должна быть выведена ровно один раз. Если ответов несколько, разрешается вывести любой из них.
4 1 2 3
111010101100
2 3 0 4
00011000011000
1 2 0 4
Impossible
В первом примере один из подходящих вариантов выкладывания следующий:
- полностью чёрная доминошка (тип 2);
- чёрно-белая доминошка, чёрный квадрат левее (тип 3);
- чёрно-белая доминошка, чёрный квадрат левее (тип 3);
- чёрно-белая доминошка, чёрный квадрат левее (тип 3);
- полностью чёрная доминошка (тип 2);
- полностью белая доминошка (тип 1).
Таким образом, получится 4 отрезка чёрного цвета, что и необходимо для победы в игре.
