ICPC Strikes Again

International Concrete Projects Company (ICPC) is a construction company that specializes in building houses for the high-end market. Thanks to a very efficient land-division method it has used in its housing projects since last year, it is the most profitable company in the world.

Recently there was chaos at ICPC: employees refused to work, arguing that they were not paid enough. Worried about losing profit to the strike, the board proposed a new way to compute salaries, which everyone happily accepted.

A worker's salary reflects how significant the tasks he or she performs are, and this significance depends on how the tasks relate to one another.

We say a task $X$ depends on a task $Y$ if either (i) $X$ depends directly on $Y$, or (ii) there is a task $Z$ such that $X$ depends directly on $Z$ and $Z$ depends on $Y$. Because every task at ICPC must be completed, the dependence relation contains no cycles. A single task may also be performed by more than one worker.

Each task has a basic significance that reflects its importance (for example, developing the efficient land-division method matters more than building the houses themselves). The significance of a task $T$ is defined as the basic significance of $T$ plus the significance of every task that depends directly on $T$. In particular, if no task depends directly on $T$, then its significance equals its basic significance.

A worker's salary is the sum of the significances of all the tasks the worker performs that do not depend on any other task the same worker performs. In other words, if a worker $W$ performs a task $X$, the significance of $X$ is added to $W$'s salary exactly when there is no other task $Y$ that $W$ also performs and on which $X$ depends.

Help ICPC determine the salary of each employee.

The input contains several test cases.

The first line of a test case contains two integers $T$ and $E$: the number of tasks and the number of employees ($1 \le T \le 1000$ and $1 \le E \le 1000$). Tasks are numbered from $1$ to $T$ and employees from $1$ to $E$.

Then follow the descriptions of tasks $1$ to $T$, in ascending order. Each task is described by two lines. The first line contains three integers $BS$, $ND$, and $NE$: the basic significance of the task, the number of tasks that depend directly on it, and the number of employees who perform it ($1 \le BS \le 1000$, $0 \le ND < T$, and $1 \le NE \le E$). The second line contains $ND + NE$ integers: first the $ND$ tasks that depend directly on this task, then the $NE$ employees who perform it.

Input ends with a line containing $T = E = 0$, which must not be processed.

Answer the test cases in the order they are given. For each test case print:

• a single line containing five stars *****, marking the start of the case;
• for each employee $i$, a line with two integers $i$ and $s$ separated by a single space, meaning that employee $i$ has a salary of $s$.