Problem D. Decision tree for matching

Author:A. Baranov   Time limit:1 sec
Input file:Standard input   Memory limit:256 Mb
Output file:Standard output  

Statement

Let we have set of the N strings of the same length are consisted by 0 and 1. Next some previously unknown string from this set will be selected, whose index need to guess.

It is required to define optimal in the worst case sequence of compares that allows to recognize index of the input string. Result need presented as decision tree.

Each non leaf node of this tree contains i — position number in which comparison need to perform. It has exactly 2 childs (for each character of the alphabet).

If in the i-th position of the string there is a character with the number k, transition to the appropriate subtree where the search will be continued is performed.

Leafs of this tree correspond to terminal states of search and contain indices of recognized strings.

Input format

Input data contains N, followed by exactly N strings of the original set.

Output format

Output data must contain decision tree written in the next format.

Leaf node starts from symbol '=', followed by string number
(indices of strings starting by zero).

Non-leaf node starts from '>',
followed by position number in which comparison will be performed.
(position starting by zero).

Next the according subtree is written in same way.

Constraints

It is guaranteed that all strings of the original set are distinct.
Their length does not exceed 32.

2 ≤ N ≤ 16

Sample tests

No. Standard input Standard output
1
5
0010111000
0111101101
0110110001
0011100101
0010111101
> 9
= 0
> 6
> 7
= 2
= 3
> 5
= 1
= 4
2
3
000
111
110
> 2
> 1
= 0
= 2
= 1

0.086s 0.013s 13