For a city, the drainage system is an extremely important component.

One day, Little C obtained the design diagram of a city's drainage system. The drainage system consists of $n$ drainage nodes (numbered from $1$ to $n$) and several one-way drainage pipes. Each drainage node has several pipes used to collect sewage from other drainage nodes (referred to as the node's collection pipes), and several pipes to discharge sewage to other drainage nodes (referred to as the node's discharge pipes).

Among the nodes in the drainage system, there are $m$ sewage intake ports, numbered $1, 2, \dots, m$. Sewage can only flow into the drainage system from these intake ports, and these nodes have no collection pipes. There are also several final drainage outlets in the drainage system that transport sewage to a sewage treatment plant; nodes with no discharge pipes can be considered final drainage outlets.

Currently, each sewage intake port has received $1$ ton of sewage. After sewage enters a node, it flows equally into each of the current node's discharge pipes toward other drainage nodes, and the final drainage outlets discharge the sewage out of the system.

Now, Little C wants to know how much sewage is discharged by each final drainage outlet in the city's drainage system. The city's drainage system is scientifically designed, and the pipes do not form loops, meaning that sewage will not circulate.

Input

The input is read from the file water.in.

The first line contains two integers $n$ and $m$, separated by a single space, representing the number of drainage nodes and the number of intake ports, respectively.

The next $n$ lines each describe all the discharge pipes of node $i$. The first integer $d_i$ in each line represents the number of discharge pipes, followed by $d_i$ integers separated by single spaces, $a_1, a_2, \dots, a_{d_i}$, representing the target drainage nodes of the pipes in order.

It is guaranteed that there will not be two pipes with the same starting node and target node.

Output

The output is written to the file water.out.

Output several lines, giving the volume of sewage discharged by each final drainage outlet in ascending order of their node numbers. The volume should be output in fractional form, i.e., each line outputs two integers $p$ and $q$ separated by a single space, representing the discharged sewage volume as $\frac{p}{q}$. It is required that $p$ and $q$ are coprime, and $q$ must be output even if $q = 1$.

Examples

Input 1

5 1
2 3 2 3 5
3 2 4 5
4 2 5 4
5 0
6 0

Output 1

4 1 3
5 2 3

Note 1

Node 1 is an intake port; nodes 4 and 5 have no discharge pipes, so they are final drainage outlets. After 1 ton of sewage flows into node 1, it flows equally to nodes 2, 3, and 5, with each node receiving $\frac{1}{3}$ ton of sewage. The $\frac{1}{3}$ ton of sewage flowing into node 2 flows equally to nodes 4 and 5, with each node receiving $\frac{1}{6}$ ton of sewage. The $\frac{1}{3}$ ton of sewage flowing into node 3 flows equally to nodes 4 and 5, with each node receiving $\frac{1}{6}$ ton of sewage. Finally, node 4 discharges $\frac{1}{6} + \frac{1}{6} = \frac{1}{3}$ ton of sewage, and node 5 discharges $\frac{1}{3} + \frac{1}{6} + \frac{1}{6} = \frac{2}{3}$ ton of sewage.

Examples 2

See water/water2.in and water/water2.ans in the contestant directory.

Examples 3

See water/water3.in and water/water3.ans in the contestant directory.

Constraints

For all test cases, it is guaranteed that $1 \le n \le 10^5$, $1 \le m \le 10$, and $0 \le d_i \le 5$. It is guaranteed that in the process of sewage flowing from an intake port to a final drainage outlet, it will not pass through more than 10 intermediate drainage nodes (excluding the intake ports and final drainage outlets).