Christmas Gifts

Every year parents face a pleasant headache: preparing Christmas gifts for their children. Because each child compares what the others received, the parents must choose gifts so that no child envies another.

Before going shopping, the parents announce a fixed pool of candidate gifts and tell the children that each of them will receive some subset of that pool. Each child then replies with a condition that must hold for them to be happy. A child's condition is stated relative to the gifts their siblings will get. The parents want to satisfy every child's condition while giving each child the smallest possible set of gifts.

Every condition is a conjunction:

• a child needs at least (α1 and α2 and ... and αk)

where each αi is one of:

• [type 1] a constant subset of the candidate gifts;
• [type 2] a sibling's name, meaning that sibling's gifts;
• [type 3] the common-things-of two operands, each of type 1 or type 2, meaning the intersection of their gift sets;
• [type 4] a sibling's name followed by except-for a constant subset, meaning that sibling's gifts with the given constant subset removed.

"Needs at least (α1 and ... and αk)" means the child's gift set must contain every αi, so the smallest satisfying set is exactly the union of all αi. Because the αi may refer to other children's gifts, the sets are defined mutually; take the smallest assignment that satisfies all conditions at the same time (it always exists and is unique).

Example. For three children {X, Y, Z} and three candidate gifts {a, b, c}:

• X needs at least ({a, b} and common-things-of(Y, Z))
• Y needs at least (common-things-of(Z, {b, c}))
• Z needs at least ({a} and (X except-for {c}))

The smallest gifts are {a, b} for X, {b} for Y, and {a, b} for Z.

The input contains T test cases. The first line holds T. Gift candidates are numbered from 1 to n (1 ≤ n ≤ 1000). Children are numbered from 1 to m (1 ≤ m ≤ 100).

The input is a sequence of whitespace-separated integers, described below line by line:

• The first line contains T.
• Each test case begins with a line holding two integers: n (the number of candidate gifts) and m (the number of children).
• The children's conditions then follow in order: child 1, child 2, ..., child m.

Each child's condition is given as:

• A line with two integers: the child's identification number and the number of parts αi in the condition.

• Then one line per part αi. Each αi line begins with a type marker: -1 for type 1, -2 for type 2, -3 for type 3, -4 for type 4.

• [type 1] -1 is followed by a count k and then k integers listing a constant set of gifts. For example, -1 2 1 2 denotes the set {1, 2}.

• [type 2] -2 is followed by one integer, a sibling's identification number. For example, -2 2 denotes sibling 2's gifts.

• [type 3] -3 is followed by two operands, each written in the type-1 or type-2 format. For example, -3 -2 3 -1 2 2 3 denotes the intersection of sibling 3's gifts and the set {2, 3}; -3 -2 2 -2 3 denotes the intersection of sibling 2's and sibling 3's gifts.

• [type 4] -4 is followed by a type-2 operand and then a type-1 operand. For example, -4 -2 1 -1 1 3 denotes sibling 1's gifts except-for {3}.

Print the answers for the test cases in order. For each test case, print one line per child in increasing order of identification number. Each line begins with the child's identification number, followed by that child's gift numbers in increasing order. If a child receives no gifts, print only the child's identification number.