Задача D. Decision tree for matching ≡

Условие

Пусть имеется набор из N строк одинаковой длины, состоящих из нулей и единиц. Далее из указанного набора будет выбрана некоторая заранее неизвестная строка, для которой необходимо угадать ее порядковый номер.

Требуется определить оптимальную в худшем случае последовательность сравнений, позволяющую однозначно распознать номер входной строки. Результат следует представить в виде дерева решений.

Каждый нелистовой узел такого дерева включает в себя номер позиции i, в которой необходимо произвести сравнение, и имеет число потомков, равное числу символов бинарного алфавита.

В случае, если в i-й позиции строки встречается символ с номером k, осуществляется переход в соответствующее поддерево, где и продолжается поиск.

Листы такого дерева соответствуют конечным состояниям поиска и хранят номера распознанных строк.

Формат входных данных

Во входных данных указано число N, за которым следует ровно N строк исходного набора.

Формат выходных данных

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

Описание листового узла начинается с символа '=', за которым указывается номер строки
(нумерация строк начинается с нуля).

Для нелистового узла вначале идет символ '>',
после чего указан номер позиции, с которой нужно продолжить сравнение
(позиции также нумеруются с нуля).

Далее аналогичным образом записывается соответствующее поддерево.

Ограничения

Гарантируется, что все строки исходного набора различны,
а их длины не превосходят 32.

2 ≤ N ≤ 16

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

5
0010111000
0111101101
0110110001
0011100101
0010111101

> 9
= 0
> 6
> 7
= 2
= 3
> 5
= 1
= 4

3
000
111
110

> 2
> 1
= 0
= 2
= 1