Description
Mr. Lu is a famous magician. There’s a poker magic tutorial on his youtube channel.
There’re N stacks of cards on the table at begining.
And then, Mr. Lu make M actions on these card stacks.
There’s only two kinds of actions Merge and Cut:
- Merge x y: put the x-th card stack on the top of y-th card stack.
- Cut x i: cut the x-th card stack into two stacks. One is the card stack contains ( 1~i )-th cards of original stack. The other one is the remaining. The former’s index will be x, the latter’s will be (x+1)
- The indexes of stacks and cards will be changed after Merge and Cut.
For example:
As a lazy CS student, you only focus on the result.
Therefore, you decide to write a program to compute the final state of card stacks.
It’s partial judge for this problem.
Please download the code at the bottom to see the interface and main function.
You have to implement a data structure like below:
Input
Two integer N,M on the first line.
For each of the next N lines, there’re several integers Ni and Ci,1,Ci,2...Ci,Ni.
Ni means the number of cards in the i-th stack.
Ci,j denotes the j-th card of i-th stack.
The folloing M lines contains one action per line.
Every Action is one of “Merge x y” or “Cut x i”.
It’s guaranteed that:
- 1 ≤ N, M ≤ 9000
- ∑ Ni ≤ 4∗104
- Ci,j is non-negative integer.
- In “Merge x y” action:
- the x, y-th stacks always exist.
- x is not equal to y.
- In “Cut x i” action:
- the x-th stack always exists.
- i is always between 1 and Nx - 1.
- There’s at least 1 card in each card stack.
Output
Print the card stacks by the order of index.
One line for one card stack.
Please refer to the sample input/output for the precise format.
There is a ‘\n’ at the end of each line.