题目描述

小部件工厂生产几种不同类型的小部件。

每个小部件都是精心制作而成。

制作小部件所需的时间取决于其类型：简单小部件仅需要 3 天，但最复杂的小部件可能需要多达 9 天。

工厂目前处于完全混乱的状态：最近，工厂被一位新主人收购，新主人解雇了几乎所有员工。

新员工对制作小部件毫无经验，没有人清楚制作每个不同类型的小部件分别需要多少天。

当客户订购小部件，工厂却无法告诉客户生产所需商品需要多少天时显得十分尴尬。

幸运的是，这里有记录记载了每个工人开始制作的日期，完成制作的日期以及制作的小部件型号。

但是问题是记录没有明确记载工人开始和完成工作的确切日期，只记录了该天是星期几。

尽管如此，这些信息也是有些帮助的：例如，如果一个人在星期二开始制作一个 41 型小部件，并在周五完成，那么我们就知道了制作一个 41 型小部件需要 4 天时间（因为最多不超过 9 天，所以不可能是 11 天或更多）。

您的任务是从这些记录中（如果可能）找出制作不同类型的小部件所需的天数。

输入格式

输入包含多组测试用例。

每个测试用例的第一行包含两个整数 n 和 m，分别代表小部件的型号总数以及记录总数。

接下来是对 m 个记录的描述。

每个记录占两行，第一行描述该名工人制作的小部件总数 k 以及他开始制作和完成制作具体是星期几。

一周的日子由字符串 MON，TUE，WED，THU，FRI，SAT 和 SUN 来表示。

第二行包含用空格分隔的 k 个整数，表示该工人具体制作了哪些类型的部件。

如下面的例子中，这名工人星期三开始工作，星期日结束工作，期间先后完成制作了型号 13，型号 18，型号 1，型号 13 四个小部件。

4 WED SUN 
13 18 1 13 

每名工人一周工作 7 天。

当输入用例 n=m=0 时，表示输入终止，且该用例无需处理。

输出格式

每个测试用例输出一行结果，结果包含 n 个用空格隔开的整数，表示制作每个小部件所需的天数。

如果测试用例有多种可能结果，则输出 Multiple solutions.。

如果无解，则输出 Inconsistent data.。

样例

2 3
2 MON THU
1 2
3 MON FRI
1 1 2
3 MON SUN
1 2 2
10 2
1 MON TUE 
3
1 MON WED
3
0 0

8 3
Inconsistent data.

数据范围

$1≤n,m≤300, 1≤k≤10000$

来源

• POJ2947
• ICPC CERC 2005
• 算法竞赛进阶指南