The Problem

袁源在"袁源与苹果(二)"中把苹果按重量排好以后,从中挑选出n个苹果,他们的重量分别是1,2,3,4……n。接下来他把所有苹果的顺序打乱,然后在苹果上刻上标号:a、b、c、d.....接着再次使用他的天平来称量苹果。不过这次他在每次称量时都把所有苹果分为两堆,分别放在天平的两端,然后根据天平读出两堆苹果的重量关系。现在他给出每次称量的结果,要你根据这些结果计算出每个苹果的重量。

输入

本题包括多组测试数据。每组测试数据的第一行为两个整数 n 和 m (1<=n<=26,1<=m<=1000),n代表所有的苹果数,m代表称量的次数。苹果的重量分别为1,2,3,4……n(当然顺序可能不是这样)。第一行后是m行称量,每次称量包括n+1个用空格分开的字符,分别是n个苹果的标号和一个'>','<'或'=',代表左右两堆苹果的关系。当 n = m = 0 时输入结束,并且这组数据不包括在需要计算的数据中。

输出

对应与每一组输入,输出一行。如果没有解,输出"No solution possible!";否则输出"Solution:",接下来是n个苹果的重量大小,按苹果的标号顺序输出(即先输出a代表的苹果的重量,接下来是b代表的苹果的重量……)。如果有多组解的话,输出一种使第一个苹果的重量最小,然后使第二个苹果的重量最小……

样例输入

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
0 0

样例输出

Solution: 1 3 2
Solution: 1 3 2