Problem A: Escape from Tut's Tomb

Congratulations Indiana: You have successfully penetrated Tut's inner chamber and bask in untold fortune and glory. But alas, your clumsy sidekick has tripped a booby trap and the only way to save both of your lives is to solve the following puzzle quickly.

Before you sit n gold sphinxes of distinct integer weights 1...n. In order to escape you must place them in the proper order on the n stones in front of you. Your awkward but clever sidekick has deciphered some hieroglyphs on the wall next to you and discovered that they contain various weighings of the sphinxes. Use this information to deduce the proper order.

Input

Input file contains several sets of input. The description of each set is given below:

The first line contains two numbers n and m (1 <= n <= 26, 1 <= m <= 10000) where n is the number of sphinxes and m is the number of weighings. The next m lines are the weighings. For convenience, the stones have been labelled alphabetically. Each line contains n letters divided by a <, =, or > where the separator indicates the sphinxes that go on the lettered stones on the left are less, equal to, or greater than in weight than the sphinxes on the right respectively.

Input is terminated by end of file.

Output

If there is no solution print No solution possible! and prepare to die. Otherwise, print Solution: followed by the weight of the sphinxs that go on the stones ordered alphabetically. If more than one solution exists, find the solution that minimizes the weight on the first stone, then the second stone, etc.

Sample Input

3 5
a c = b
a c = b
b c > a
a c = b
c < a b
3 5
a c = b
a c = b
b c > a
a c = b
c < a b

Sample Output

Solution: 1 3 2
Solution: 1 3 2