일식 요리

도널드 대령은 작은 일식당을 운영한다. 그리고 그 식당의 유일한 요리사이기 때문에, 손님이 주문한 모든 요리를 직접 만든다.

기본적으로 주문은 선착순 원칙에 따라 처리한다. 각 요리를 만드는 데는 정해진 시간이 걸린다. 손님은 한 번에 여러 요리를 주문할 수 있으므로, 대령은 조리 시간이 가장 긴 요리부터 만들기 시작한다. 조리 시간이 같은 요리가 두 개 이상 있으면, 식당 메뉴판에 적힌 순서대로 만든다. (손님이 주문한 순서는 상관없다.) 손님이 주문한 모든 요리를 완성하면, 곧바로 웨이트리스에게 넘겨 손님에게 서빙한다. 서빙에 걸리는 시간은 무시할 수 있다. 그 후 다음 주문을 받을 준비가 된다.

한편, 어떤 주문을 조리하는 동안 다른 손님이 와서 요리를 주문할 수도 있다. 효율을 위해 그는 가능하면 같은 종류의 여러 요리를 한꺼번에 만들기로 했다. 새 요리를 만들기 시작할 준비가 되면, 그때까지 접수된 주문(정확히 그 시각에 접수된 주문이 있다면 그것도 포함)을 살펴보고, 다음에 만들 같은 요리의 개수를 센다. 한 번에 몇 개를 만들든 조리 시간은 같다. 안타깝게도 주방의 용량이 한정되어 있어, 요청된 개수만큼 한꺼번에 만들 수 없는 경우가 있다. 그런 경우에는 가능한 한 많이 만든다.

여러분의 과제는 이 식당을 시뮬레이션하는 프로그램을 작성하는 것이다. 메뉴판의 요리 목록과 손님들의 주문 및 접수 시각이 주어지면, 각 손님이 서빙받는 시각의 목록을 출력해야 한다.

입력에는 $110$개 이하의 데이터 세트가 들어 있다. 각 데이터 세트의 형식은 다음과 같다:

$N$ $M$

$\mathit{Name}_1$ $\mathit{Limit}_1$ $\mathit{Time}_1$

$\ldots$

$\mathit{Name}_N$ $\mathit{Limit}_N$ $\mathit{Time}_N$

$T_1$ $K_1$ $\mathit{Dish}_{1, 1}$ $\ldots$ $\mathit{Dish}_{1, K_1}$

$\ldots$

$T_M$ $K_M$ $\mathit{Dish}_{M, 1}$ $\ldots$ $\mathit{Dish}_{M, K_M}$

여기서 $N$ ($1 \le N \le 20$)과 $M$ ($1 \le M \le 100$)은 각각 메뉴판 항목의 수와 도널드가 받을 주문의 수를 나타낸다. 각 $\mathit{Name}_i$는 메뉴판 $i$번째 항목의 요리 이름으로, 알파벳 최대 $20$자로 이루어진 고유한 이름이다. 정수 $\mathit{Limit}_i$ ($1 \le \mathit{Limit}_i \le 10$)는 대령이 동시에 만들 수 있는 해당 요리의 최대 개수다. 정수 $\mathit{Time}_i$ ($1 \le \mathit{Time}_i \le 1000$)는 $i$번째 항목의 요리(여러 개일 수도 있다)를 만드는 데 걸리는 시간이다. 정수 $T_j$ ($1 \le T_j \le 10^8$)는 $j$번째 주문이 접수된 시각이다. 정수 $K_j$ ($1 \le K_j \le 10$)는 $j$번째 주문에 포함된 요리의 수다. 그리고 각 $\mathit{Dish}_{j, k}$는 $j$번째 주문에 있는 요리 하나를 나타낸다.

주문에 나오는 모든 요리는 메뉴판에 있다고 가정해도 된다. 다만 각 주문에 같은 요리가 여러 번 나올 수 있다는 점에 유의하라. 주문은 $T_j$가 증가하는 순서로 주어지며, 두 주문이 같은 시각에 접수되는 경우는 없다.

입력은 두 개의 0이 들어 있는 한 줄로 끝난다. 이 줄은 데이터 세트의 일부가 아니므로 처리하지 않는다.

프로그램은 각 데이터 세트마다 $M$줄을 출력해야 한다. 이 출력의 $i$번째 줄에는 $i$번째 주문이 완성되어 손님에게 서빙되는 시각을 나타내는 정수 하나가 들어가야 한다.

연속한 두 데이터 세트 사이에는 빈 줄을 하나 출력한다.