Поликарп проснулся рано утром и, по своему обыкновению, посмотрел на свои настольные часы, чтобы узнать, сколько времени. Однако, к глубокому разочарованию нашего героя, выяснилось, что его сосед по комнате положил свои вещи на стол перед часами, тем самым частично ограничивая видимость циферблата для Поликарпа. Вставать с кровати было лень, поэтому Поликарп задался вопросом — сколько различных валидных значений времени могут показывать часы в текущий момент, исходя из видимой для Поликарпа части циферблата? Вычислять это ему тоже было лень, поэтому он попросил вас помочь ему с этим.
Часы Поликарпа показывают время в формате hh:mm, то есть на циферблате изображено два двузначных числа, разделённых двоеточием — число часов и число минут. На каждой позиции для цифры имеется $$$7$$$ независимых сегментов. Каждый из них может гореть или не гореть. Цифры отображаются с помощью некоторых комбинаций горящих сегментов. Вот как на часах отображаются цифры от $$$0$$$ до $$$9$$$:
В этой задаче каждый сегмент каждой цифры может либо гореть, либо не гореть, либо быть скрыт от зрения Поликарпа (то есть его состояние неизвестно).
Возможно такое, что горящий набор сегментов одной позиции, видимый Поликарпу, не соответствует ни одной цифре. Это означает, что часы сломаны, и в ответе будет $$$0$$$ валидных значений времени.
Обратите внимание, что на часах Поликарпа первая цифра (цифра десятков часов) всегда пишется! То есть время «полвторого ночи» будет на часах выглядеть как 01:30. Отсутствие на циферблате цифры десятков часов считается невалидной конфигурацией!
Каждая позиция для цифры на циферблате во входных данных представлена матрицей размера $$$9 \times 6$$$, состоящей из символов ., 1 и X. Вот так выглядит матрица для цифры $$$8$$$:
Формально, в индексации с единицы вертикальные сегменты начинаются во $$$2$$$-й, а заканчиваются в $$$4$$$-й, а также начинаются в $$$6$$$-й, а заканчиваются в $$$8$$$-й строчках $$$1$$$-го и $$$6$$$-го столбцов, а горизонтальные — начинаются во $$$2$$$-м, а заканчиваются в $$$5$$$-м столбцах $$$1$$$-й, $$$5$$$-й и $$$9$$$-й строк.
Если какой-то сегмент не горит, то на его месте в матрице будут символы . вместо единиц. Например, вот как выглядит на циферблате позиция, на которой не горит ни один сегмент:
Если какой-то сегмент скрыт от зрения Поликарпа, то на его месте в матрице будут символы X вместо единиц. Например, вот как выглядит на циферблате позиция, на которой все сегменты скрыты от зрения Поликарпа:
Матрицы, соответствующие отдельным позициям на циферблате, во входных данных объединены в общую матрицу размера $$$9 \times 29$$$, задающую весь циферблат. В этой общей матрице позиции, соответствующие десяткам и единицам часов, а также десяткам и единицам минут, разделены столбиком из точек. Число часов и число минут разделены тремя столбцами, содержащими точки, а также два символа * по центру (формально, в индексации с единицы — в $$$4$$$-й и $$$6$$$-й строках $$$15$$$-го столбца), символизирующих двоеточие. Вот, например, как отображается время 18:08 в описанном формате:
Входные данные представляют собой $$$9$$$ строк, в каждой по $$$29$$$ столбцов, содержащие циферблат в описанном выше формате.
Гарантируется, что ни один сегмент не горит частично. То есть каждый сегмент либо полностью горит, либо полностью не горит, либо полностью скрыт от взора Поликарпа.
В первой строке выведите одно целое число $$$k$$$ — количество валидных моментов времени, которые могут показывать часы Поликарпа в заданных условиях. В следующих $$$k$$$ строках выведите сами валидные моменты времени в формате hh:mm, упорядоченные лексикографически, по одному в строке. Если часы Поликарпа сломаны, то просто выведите 0 в единственной строке.
.1111............1111...1111......1......1........1.1....1.....1......1........1.1....1.....1......1.*......1.1....1.1111............1111...XXXX.X....X......1.*......1.1....1X....X......1........1.1....1X....X......1........1.1....1.XXXX............1111...1111.
2 21:30 21:38
.1111........................1....1.1....1........1.1....11....1.1....1........1.1....11....1.1....1.*......1.1....1........1111.................1....1......1.*......1.X....X1....1......1........1.X....X1....1......1........1.X....X.1111...................XXXX.
0
.....................................................................................................*.........................................................*.....................................................................................................
0
.1111...1111.....1111...1111.1....1.1....1...1....1.1....11....1.1....1...1....1.1....11....1.1....1.*.1....1.1....1.1111...1111.....1111...1111.1....1.1....1.*.1....1.1....11....1.1....1...1....1.1....11....1.1....1...1....1.1....1.1111...1111.....1111...1111.
0
В первом примере цифры единиц часов и десятков минут определены однозначно. На месте цифры единиц минут может быть как цифра $$$0$$$, так и цифра $$$8$$$. Комбинация известных Поликарпу горящих сегментов на позиции десятков часов подходит и для цифры $$$2$$$, и для цифры $$$3$$$, но цифра $$$3$$$ не может стоять на этой позиции, так как в сутках всего $$$24$$$ часа.
Во втором примере комбинация видимых Поликарпу сегментов единиц минут не может быть частью ни одной цифры, следовательно, часы сломаны.