题目描述

在购买新软件产品时，消费者通常不会期望软件完全没有漏洞。你能想象购买一辆方向盘只能向右转的汽车吗？或者一个只能播放乡村音乐CD的CD播放器？很可能不会。但对于软件系统来说，即使它们不能按预期运行，似乎也是可以接受的。事实上，许多软件公司已经养成了在新产品发布后每隔几周就发布补丁修复漏洞的习惯（甚至对这些补丁收费）。

Tinyware公司就是这样的一家公司。今年夏天发布了一款新的文字处理软件后，他们一直在制作补丁。就在这个周末，他们意识到发布的补丁存在一个大问题。虽然所有补丁都能修复一些漏洞，但它们通常依赖于其他漏洞的存在才能安装。这是因为为了修复一个漏洞，补丁利用了程序由于另一个漏洞而产生的特殊行为。

更正式地说，情况是这样的。Tinyware在软件中共发现了n个漏洞B = {b1, b2, ..., bn}，并且发布了m个补丁p1, p2, ..., pm。要将补丁pi应用到软件中，漏洞集合Bi+中的漏洞必须存在于软件中，而漏洞集合Bi-中的漏洞必须不存在（当然Bi+ ∩ Bi- = Φ）。然后，补丁会修复集合Fi-中的漏洞（如果它们存在）并引入集合Fi+中的新漏洞（同样，Fi+ ∩ Fi- = Φ）。

Tinyware的问题很简单。给定软件的原始版本（包含B中的所有漏洞），是否存在一个补丁序列可以应用到软件上，最终得到一个没有漏洞的软件版本？如果存在，假设每个补丁应用需要一定的时间，最快的序列需要多长时间？

输入格式

输入包含多个产品描述。每个描述的第一行是两个整数n和m，分别表示漏洞数量和补丁数量。这些值满足1 <= n <= 20和1 <= m <= 100。接下来是m行，按顺序描述m个补丁。每行包含一个整数（应用补丁所需的时间，单位为秒）和两个长度为n的字符串。

第一个字符串描述应用补丁前必须存在或不存在的漏洞。该字符串的第i个字符如果是'+'，表示漏洞bi必须存在；如果是'-'，表示漏洞bi必须不存在；如果是'0'，表示漏洞bi是否存在无关紧要。

第二个字符串描述补丁修复和引入的漏洞。该字符串的第i个字符如果是'+'，表示补丁引入了漏洞bi；如果是'-'，表示补丁修复了漏洞bi（如果存在）；如果是'0'，表示补丁对漏洞bi没有影响（如果之前存在，仍然存在；如果之前不存在，仍然不存在）。

输入以一行n = m = 0结束，该测试用例不需要处理。

输出格式

对于每个产品描述，首先输出产品编号。然后输出是否存在一个补丁序列可以移除所有漏洞。注意，在这样的序列中，一个补丁可以被多次使用。如果存在这样的序列，按照样例输出的格式输出最快序列所需的时间。如果不存在这样的序列，输出“Bugs cannot be fixed.”。

每个测试用例后输出一个空行。

示例输入1

3 3
1 000 00-
1 00- 0-+
2 0-- -++
4 1
7 0-0+ ----
0 0

示例输出1

Product 1
Fastest sequence takes 8 seconds.

Product 2
Bugs cannot be fixed.

来源

1998年西南欧区域赛（Southwestern European Regional Contest）