Donald 上校经营着一家小型日本料理店。由于他是店里唯一的厨师，他负责烹饪顾客点的所有菜品。

基本上，他按照先来后到的原则处理订单。准备每道菜都需要一些规定的时间。由于顾客一次可以点多道菜，上校会从准备时间最长的菜开始烹饪。如果有多道菜的准备时间相同，他会按照餐厅菜单上列出的顺序来制作这些菜。（注意：顾客点菜的顺序与烹饪顺序无关。）当他完成某位顾客点的所有菜品后，会立即将菜品交给服务员并送达给顾客。上菜时间可以忽略不计。此后，他便准备处理下一份订单。

另一方面，在他为某人的订单烹饪期间，可能会有其他顾客前来点餐。为了提高效率，他决定尽可能将同种菜品放在一起烹饪。当他准备开始烹饪一道新菜时，他会查看截至当时已接受的订单（包括恰好在此时接受的订单，如果有的话），并统计他接下来要烹饪的同种菜品的数量。无论一次准备多少道菜，烹饪所需的时间都是一样的。遗憾的是，厨房的容量有限，因此有时无法一次性准备好所需数量的菜品。在这种情况下，他只会尽可能多地准备菜品。

你的任务是编写一个程序来模拟这家餐厅。给定菜单上的菜品列表以及顾客的订单及其接受时间，你的程序应输出每位顾客被上菜的时间。

输入格式

输入包含不超过 110 组数据。每组数据格式如下：

$N$ $M$ $Name_1$ $Limit_1$ $Time_1$ ... $Name_N$ $Limit_N$ $Time_N$ $T_1$ $K_1$ $Dish_{1,1}$ ... $Dish_{1,K_1}$ ... $T_M$ $K_M$ $Dish_{M,1}$ ... $Dish_{M,K_M}$

其中，$N$ ($1 \le N \le 20$) 和 $M$ ($1 \le M \le 100$) 分别表示菜单上的条目数和 Donald 将收到的订单数。每个 $Name_i$ 是菜单中第 $i$ 个条目的菜名，由最多 20 个字母组成。整数 $Limit_i$ ($1 \le Limit_i \le 10$) 是上校同时能烹饪该种菜品的最大数量。整数 $Time_i$ ($1 \le Time_i \le 1000$) 是准备第 $i$ 个条目的菜品（或多道菜品）所需的时间。整数 $T_j$ ($1 \le T_j \le 10^8$) 是第 $j$ 份订单被接受的时间。整数 $K_j$ ($1 \le K_j \le 10$) 是第 $j$ 份订单中的菜品数量。每个 $Dish_{j,k}$ 表示第 $j$ 份订单中的一道菜。

你可以假设订单中的每道菜都在菜单中列出，但请注意，每份订单可能包含多次出现的相同菜品。订单按 $T_j$ 升序给出，且没有两份订单在同一时间被接受。

输入以包含两个零的一行结束。这不属于数据组，因此不应处理。

输出格式

对于每组数据，你的程序应输出 $M$ 行。第 $i$ 行应包含一个整数，表示第 $i$ 份订单完成并上菜给顾客的时间。

在两组连续的数据之间打印一个空行。

样例

输入 1

5 4
Ramen 3 10
Chahan 5 5
Gyoza 5 10
Rice 1 1
Soup 1 1
5 2 Ramen Gyoza
10 6 Chahan Gyoza Soup Ramen Gyoza Rice
20 1 Chahan
25 1 Ramen
0 0

输出 1

25
42
40
35