Задача A. Марсианские кассы

Автор:А. Жуплев, А. Кленин   Ограничение времени:2 сек
Входной файл:input.txt   Ограничение памяти:64 Мб
Выходной файл:output.txt  
Максимальный балл:50  

Условие

Марсианские кассовые аппараты распечатывают коды товаров на чеках в виде строки, состоящей из цифр от '0' до '9' и заглавных латинских букв от 'A' до 'F'. Все коды имеют длину N символов.

Каждый символ выводится в виде матрицы размером 5 × 7 позиций, некоторые из которых закрашиваются при печати. Символы отделяются друг от друга вертикальным рядом неокрашенных позиций. Матрицы для всех используемых символов приведены ниже ('.' (точка) обозначает неокрашенную, а '#' — закрашенную позицию):

0
.###.
#...#
#..##
#.#.#
##..#
#...#
.###.
1
...##
..#.#
.#..#
#...#
....#
....#
....#
2
.###.
#...#
....#
...#.
..#..
.#...
#####
3
.###.
#...#
....#
.###.
....#
#...#
.###.
4
#...#
#...#
#...#
#...#
.####
....#
....#
5
#####
#....
#....
####.
....#
#...#
.###.
6
.###.
#...#
#....
####.
#...#
#...#
.###.
7
#####
....#
....#
...#.
..#..
.#...
#....
8
.###.
#...#
#...#
.###.
#...#
#...#
.###.
9
.###.
#...#
#...#
.####
....#
#...#
.###.
A
..#..
.#.#.
#...#
#...#
#####
#...#
#...#
B
####.
#...#
#...#
####.
#...#
#...#
####.
C
.###.
#...#
#....
#....
#....
#...#
.###.
D
###..
#..#.
#...#
#...#
#...#
#..#.
###..
E
#####
#....
#....
####.
#....
#....
#####
F
#####
#....
#....
####.
#....
#....
#....

Однажды марсианский кассовый аппарат сломался, и распечатал один из чеков поверх другого. В результате изображения товарных кодов перекрылись, так что в каждом выведенном символе оказались закрашены точки, соответствующие символам как первого, так и второго кода.

Ваша программа должна восстановить по полученному изображению две исходные строки товарного кода или определить, что это изображение не могло быть получено перекрытием двух товарных кодов.

Рекомендуется рассмотреть частичные решения

Формат входного файла

Входной файл состоит из 7 строк по 6 × N − 1 символов каждая — изображение перекрывающихся товарных кодов.

Формат выходного файла

Выходной файл должен содержать две строки длиной по N символов — восстановленные коды товаров. Если решения не существует, вывести единственную строку IMPOSSIBLE. Если решений несколько, вывести любое из них.

Ограничения

1 ≤ N ≤ 40

Примеры тестов

Входной файл (input.txt) Выходной файл (output.txt)
1
.###..#####
#...#.#...#
#...#.#...#
.####.####.
....#.#...#
#...#.#...#
.###..####.
9B
9F
2
.###..#####
#...#.#...#
#...###...#
.####.####.
....#.#...#
#...###...#
.###..####.
IMPOSSIBLE
3
#####...#..
#####...#..
#####...#..
#####...#..
#####...#..
#####...#..
#####...#..
IMPOSSIBLE

0.124s 0.017s 13