Description
This is a normal judge problem.
You are allowed to use STL in this problem. Include <stack> & <queue> to use them and it will make your life easier.(Reference: https://en.cppreference.com/w/cpp/container/stack; https://en.cppreference.com/w/cpp/container/queue)
There are some people who like to bury their treasures, time capsules and other things that are important to them. As an EECS course student, data is important to you. This problem is simply about burying data in the ground and digging them out later.
There will be T independent cases you need to handle in one input file. For each case, the detail is defined below:
Given a ground that consists of S spots numbered from 0 to S-1. Each spot can be considered as a vertical slot that contains many layers in the ground. The layer which is closest to the surface is numbered as 1 and the next is numbered as 2, and so on.
There are totally B burying instructions. Each of them specifies a spot Si to bury Ni data which are denoted by Ni positive, one-digit integers, d1, d2, d3, …, dNi. The Ni data will be buried in the ground one by one in ascending order according to their subscript notations. When every single one of them is being buried, the data which had been already buried in the same spot will be pushing further down. (They will move to the next layer)
After all the burying instruction are finished, the data will be dug out layer-by-layer. M layers of them are required to be shown. They will be specified by M distinct integers that is sorted in the ascending order, denoted by l1, l2, l3, …, lM.
For each layer that is required to be shown, you need to print the data in each spot in ascending order according to the spot number. For some spots that don’t contain any data in the certain layer, print 0 instead.
Separate each data of the same layer with a space and after printing the data from the last spot, end the line with a newline symbol.
Show the layers in ascending order according to their subscript notations.
Input
The first line of the input file contains an integer T, representing the number of cases you need to handle.
After the first line, there will be T cases. Each of them can be broken down to 4 parts:
- The first part contains a line consist of two integers S and B, representing the number of the spots at which the data can be buried and the number of the burying instructions.
- The second part consist of B lines. Each line i contains: an integer Si, an integer Ni and Ni more positive, one-digit integers, d1, d2, d3, …, dNi.
- Si indicates the spot to bury thing at.
- Ni indicates the number of data which are going to be buried.
- d1, d2, d3, …, dNi represent the data themselves.
- The third part consist of one line that contains an integer M, which represents the total number of the layers that you need to show.
- The fourth part consists of one line that contains M distinct integers, l1, l2, l3, …, lM, which are sorted in the ascending order. They explicitly specify the layers you need to show.
It is guaranteed that: 1 ≤ T ≤ 10
And for each case, it is guaranteed that:
- 0 < S, B
- 0 ≤ Si < S (the bury spot will always be valid)
- 0 < Ni
- 0 < d1, d2, d3, …, dNi ≤ 9
- 0 < M
- 0 < l1, l2, l3, …, lM
- Test case #1 ~ #3: S ≤ 5; B ≤ 5; ∀ i < B, i ∈ ℕ0, Ni ≤10 and ∑ Ni ≤ 100;
- Test case #4: S ≤ 10; B ≤ 5; ∀ i < B, i ∈ ℕ0, Ni ≤10 and ∑ Ni ≤ 100;
- Test case #5: S ≤ 10; B ≤ 10; ∀ i < B, i ∈ ℕ0, Ni ≤10^5 and ∑ Ni ≤ 10^6;
Output
For each case, based on the parameters specified in that case (integer M, the integer S, and the distinct integers, l1, l2, l3, …, lM), you need to print M lines representing the layer l1, l2, l3, …, lM. Each of the line consists of S integers that represents the S data in that layer. For spots that don't contain data in that layer, the integers will be 0. Separate each data by a space and end the line with a new line symbol.
Hint
Think about the order of burying data and the order of printing data. Choose a more suitable data structure for your design.
The data closest to the surface of each spot will be dug out simultaneously. How can you utilize this feature?
Example Animation
