Problem D
Paper Pile Pandemonium

Photo by Christa Dodoo. Retrieved from Unsplash. Unsplash License. Source

It’s nearing the end of a busy semester, and you have piles of homework to finish. Literally. All of your homework was printed on sheets of paper (poor trees), which you laid out on your desk in a series of piles. As you were completing the assignments, you moved sheets of paper from the top of one pile to the top of another pile, and kept a diligent log as you did so to keep track of which assignments were completed.

Suddenly, you realize that some of your assignments are due in only in a few minutes, and you need to scan and turn them in now! Through all the shuffling you unfortunately lost track of where all the assignments are amongst the piles. However, your diligent log should let you determine where the assignments must be now. Can you write a program that can determine where all the assignments are now located?

Input

The first line of input contains two space-separated integers, $1 \leq N \leq 1\, 000$ and $1 \leq P \leq 1\, 000$, the number of sheets of paper, and the number of piles the sheets of paper are organized in, respectively. The next $P$ lines each begin with a single integer $0 \leq p_ i \leq N$, indicating the number of sheets of paper that were initially in the $i^{\text {th}}$ pile. That integer is followed by a space and then $p_ i$ space-separated integers in the range $[1, N]$ denoting, from left to right, the sheet numbers that appear in the pile from bottom to top. Note that sheet numbers will appear exactly once amongst all the piles, and that $\sum _{i=1}^{P} p_ i = N$ (the sum of sheets in each pile is equal to the total number of sheets, $N$).

The next line contains a single integer, $0 \leq M \leq 1\, 000$, the number of times sheets of paper were moved from one pile to another. The next $M$ lines each contain three space separated integers defining one such movement, $1 \leq s_ i \leq P$, $1 \leq d_ i \leq P$, and $1 \leq n_ i \leq N$, the source pile number, the destination pile number, and the number of sheets of paper that were moved from the top of the source pile to the top of the destination pile, respectively. When the sheets are moved, they are lifted as a group off the top of the source pile, and placed on top of the destination pile without changing their order. Note also that for all $i$, $s_ i \neq d_ i$, and it is guaranteed that number of sheets in pile $s_ i$ before the $i^{\text {th}}$ movement is greater than or equal to $n_ i$.

Output

You should output $P$ lines, with the $i^\text {th}$ line containing zero or more space-separated integers denoting, from left to right, the sheet numbers that appear in the $i^\text {th}$ pile (from bottom to top) after all movements have occurred. If there are no sheets in a pile, output an empty line.

Sample Explanation

In the first sample input, the sheets begin in the configuration below. The numbers $1$, $2$, and $3$ along the bottom indicate the pile numbers, and the numbers above indicate the position of sheets in each pile. In this case, sheets $3$, $5$, and $6$ would be visible on the tops of the piles.

There are three movements. The first movement takes two sheets from the top of pile $1$ and places them on pile $3$, resulting in the configuration below. Note that sheet $2$ remains under sheet $3$.

The second movement takes a single sheet from the top of pile $2$ and places it on pile $1$, resulting in the configuration below.

The third and final movement takes the sheet from pile $2$ and places it on top of pile $3$, resulting in the configuration below.

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

1 5

6 2 3 4

20 5
6 6 19 1 20 13 3
2 7 4
3 15 17 11
7 16 18 10 2 12 5 9
2 8 14
10
1 2 5
2 5 3
4 2 2
2 5 5
4 3 1
5 4 9
3 5 3
1 3 1
4 1 6
5 2 3

3 4 19 1 5 9
7 17 11 12
15 6
16 18 10 2 14 20 13
8