Дораскладывать косынку
Как известно, у классического пасьянса «Косынка» есть финальная стадия, когда все карты уже открыты, колоды нет, и надо просто переложить все карты на тузов. В большинстве компьютерных реализаций «Косынки» это делается автоматически, но мы предлагаем это сделать вам.
Правила этой стадии можно вкратце описать следующим образом. В пасьянсе используется стандартная колода из 52 карт. А именно, каждая карта характеризуется достоинством (в порядке возрастания: туз, 2, 3, 4, 5, 6, 7, 8, 9, 10, валет, дама, король) и мастью (червы, бубны, трефы, пики); существует ровно одна карта для каждой пары (достоинство, масть). Обратите внимание, что (в отличие от ряда других карточных игр) туз считается картой с наименьшим достоинством.
На столе определены четыре места для стопок карт — так называемые дома. На каждом доме можно формировать стопку из карт одной масти по возрастанию достоинств. А именно, если на доме пока не лежит ни одной карты, то на него можно положить любого туза. Иначе на стопку карт, лежащих на доме, можно положить следующую по достоинству карту той же масти. Например, на пикового туза можно положить пиковую двойку, поверх нее пиковую тройку и т.д.
Кроме того, есть так называемые ряды, их ровно 7 штук. В процессе раскладывания пасьянса в них могут быть закрытые и открытые карты, но на интересующем нас этапе закрытых карт нет, и в каждом ряду лежит последовательность (возможно, пустая) открытых карт. Масти карт в одном ряду могут быть различны, но достоинства должны образовывать непрерывную убывающую последовательность.
За один ход можно взять одну карту с низа любого ряда (она всегда будет иметь минимальное достоинство в этом ряду) и переложить ее на любой дом с соблюдением правил размещения карт в доме. Т.е. туза можно перекладывать только на пустой дом, а любую другую карту $X$ — только на дом, на котором уже есть стопка той же масти, и только при условии, что верхняя карта в этой стопке имеет достоинство на единицу меньше чем достоинство карты $X$.
Например, если в каком-нибудь ряду нижняя карта — это четверка пик, и на одном из домов есть стопка, наверху которой есть тройка пик, то четверку пик можно переложить на эту стопку поверх тройки пик.
Цель пасьянса — переложить все карты на дома, так, чтобы все ряды оказались пустыми.
В первой строке дано описание четырех карт — верхних карт в стопках на каждом доме. Если вместо карты записано «00», то это означает, что соответствующая стопка пуста. Гарантируется, что масти этих карт различны, и что никакие карты из стопок на домах не присутствуют в рядах, описываемых ниже.
Далее в $7$ строках следует описание рядов карт. Каждое описание начинается с целого числа $k$ ($0\le k \le 13$) — количества карт в очередном ряду. Далее перечислены $k$ карт данного ряда.
Каждая карта во входных данных представлена строкой длины 2 или 3 символа, последний символ в которой — масть, а первые 1 или 2 символа — достоинство. Достоинства обозначаются или числами от 2 до 10, или символами: J — валет, Q — дама, K — король, A — туз. Масти обозначаются следующим образом: h — червы, d — бубны, c — трефы, s — пики. Гарантируется, что каждая карта встретится в описании не более одного раза, и что положение карт удовлетворяет правилам пасьянса «Косынка».
Выведите последовательность карт в том порядке, в котором их нужно перекладывать на дома. Гарантируется, что решение существует.
Kh Ks Kd Kc 0 0 0 0 0 0 0
4h 6c 6d 5s 9 Kh Qc Jd 10c 9h 8s 7d 6s 5h 8 Ks Qd Js 10h 9c 8h 7c 6h 2 8c 7h 0 5 Kd Qs Jh 10s 9d 7 Kc Qh Jc 10d 9s 8d 7s 0
5h 6h 6s 7c 7d 7h 7s 8c 8d 8h 8s 9c 9d 9h 9s 10c 10d 10h 10s Jc Jd Jh Js Qc Qd Qh Qs Kc Kd Kh Ks
5h 5c 5d 5s 8 Kh Qc Jd 10c 9h 8s 7h 6c 0 8 Kd Qs Jh 10s 9d 8c 7d 6s 8 Ks Qh Js 10d 9c 8d 7c 6h 0 0 8 Kc Qd Jc 10h 9s 8h 7s 6d
6c 6d 6h 6s 7c 7d 7h 7s 8c 8d 8h 8s 9c 9d 9h 9s 10c 10d 10h 10s Jc Jd Jh Js Qc Qd Qh Qs Kc Kd Kh Ks
В примерах выше вывод разбит на строки для удобства чтения. Ваше решение должно выводить ответ в одной строке.
В первом примере все карты и так уже лежат на домах, никаких действий не требуется.
Во втором примере можно, например, сначала переложить пятерку червей с первого ряда на стопку на первом доме. После этого можно туда же переложить шестерку червей со второго ряда, дальше можно переложить шестерку пик с первого ряда на соответствующий дом, и т.д.
Задача на Codeforces (контест gym/102112, задача F, © Codeforces.com)