Steve runs a small restaurant in a city. Also, as he is the only cook in his restaurant, he cooks everything ordered by customers.

Basically he attends to orders by first-come-first-served principle. He takes some prescribed time to prepare each dish. As a customer can order more than one dish at a time, Steve starts his cooking with the dish that takes the longest time to prepare. In case that there are two or more dishes that take the same amount of time to prepare, he makes these dishes in the sequence as listed in the menu card of his restaurant. Note that he does not care in which order these dishes have been ordered. When he completes all dishes ordered by a customer, he immediately passes these dishes to the waitress and has them served to the customer. Time for serving is negligible.

On the other hand, during his cooking for someone’s order, another customer may come and order dishes. For his efficiency, he decided to prepare together multiple dishes of the same if possible. When he starts cooking for new dishes, he looks over the orders accepted by that time (including the order accepted exactly at that time if any), and counts the number of the same dishes he is going to cook next. Time required for cooking is the same no matter how many dishes he prepare at once. Unfortunately, he has only limited capacity in the kitchen, and hence it is sometimes impossible that the requested number of dishes are prepared at once. In such cases, he just prepares as many dishes as possible.

Your task is to write a program that simulates the restaurant. Given a list of dishes in the menu card and orders from customers with their accepted times, your program should output a list of times when each customer is served.



Input

The input contains multiple data sets. Each data set is in the format below:


N M
Name1 Limit1 Time1
...
NameN LimitN TimeN
T1 K1 Dish1,1 . . . Dish1,K1
...
TM KM DishM,1 . . . DishM,KM


Here, N (1 ≤ N ≤ 20) and M (1 ≤ M ≤ 100) specify the number of entries in the menu card and the number of orders that Steve will receive, respectively; each Namei is the name of a dish of the i-th entry in the menu card, which consists of up to 20 alphabetical letters; Limiti (1 ≤ Limiti ≤ 10) is the number of dishes he can prepare at the same time; Timei (1 ≤ Timei ≤ 1000) is time required to prepare a dish (or dishes) of the i-th entry; Tj (1 ≤ Tj ≤ 10000000) is the time when the j-th order is accepted; Kj (1 ≤ Kj ≤ 10) is the number of dishes in the j-th order; and each Dishj,k represents a dish in the j-th order.

You may assume that every dish in the orders is listed in the menu card, but you should note that each order may contain multiple occurrences of the same dishes. The orders are given in ascending order by Tj , and no two orders are accepted at the same time.

The input is terminated with a line that contains two zeros. This is not part of data sets and hence should not be processed.

Output

Your program should produce the output of M -lines for each data set. The i-th line of the output should contain a single integer that indicates the time when the i-th order will be completed and served to the customer.

Print a blank line between two successive data sets.

Example

Input

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


Output

25
42
40
35
#include <iostream>
#include <string>
#include <map>
#include <queue>
#include <algorithm>
using namespace std;

enum EVENT{ORDER, COOKED};

class Event
{
public:
	int c,t,s,id;
	EVENT e;
	
	Event(int c, int t, int s, int id, EVENT e)
	:c(c),t(t),e(e),s(s),id(id)
	{}
	
	bool operator<(const Event& a) const
	{
		if(t!=a.t) return t>a.t;
		if(e!=a.e) return e<a.e;
		if(c==a.c) return s>a.s;
		return c>a.c;
	}
};

class Order
{
public:
	int id,pt;
	Order(int id, int pt)
	:id(id),pt(pt)
	{}
	
	bool operator<(const Order& a) const
	{
		if(pt!=a.pt) return pt>a.pt;
		return id<a.id;
	}
};

int main()
{
	bool f=true;
	int M,N;
	while(cin >> M >> N, (M||N))
	{
		if(!f) cout << endl;
		f=false;
		
		int limit[20], time[20];
		map<string, int> d;
		for(int i=0; i<M; i++)
		{
			int l,t;
			string n;
			cin >> n >> l >> t;
			d[n]=i;
			
			limit[i]=l; time[i]=t;
		}
		
		priority_queue<Event> q;
		
		int order[100],cooked[100]={0},cookid=-1,cooking=0,cooktime=-1,served[100],pretime=-1;
		for(int i=0; i<N; i++)
		{
			int t,o;
			cin >> t >> o;
			order[i]=o;
			vector<Order> seq;
			for(int j=0; j<o; j++)
			{
				string n;
				cin >> n;
				seq.push_back(Order(d[n], time[d[n]]));
			}
			sort(seq.begin(), seq.end());
			for(int j=0; j<seq.size(); j++)
			{
				q.push(Event(i,t,j,seq[j].id,ORDER));
			}
		}
		while(!q.empty())
		{
			Event e=q.top(); q.pop();
			if(e.e==ORDER)
			{
				if(cookid==e.id&&cooking<limit[e.id]&&pretime==e.t||cooking==0)
				{
					int tm=e.t+time[e.id];
					pretime=e.t;
					cooktime=tm;
					cooking++;
					cookid=e.id;
					q.push(Event(e.c, tm,e.s, e.id,COOKED));
				}
				else
				{
					q.push(Event(e.c, cooktime,e.s, e.id,e.e));
					continue;
				}
			}
			else
			{
				cooking--;
				cooked[e.c]++;
				if(cooked[e.c]==order[e.c])
					served[e.c]=e.t;
			}
		}
		
		for(int i=0; i<N; i++)
			cout << served[i] << endl;
	}
}