Description
After gathering a lot of data, the Survey Corps returned to discuss their strategy. However, because they use the quadtree structure, all their data comes in the form of numbers; therefore they have to reverse their quadtree algorithm in order to retrieve the battlefield data they had just collected.
* It is recommended to finish the "Attack on Quadtree" question beore attempting this one **
As a referesher, to use the quadtree structure, we must first divide the initial area to 4 separate quadrants (upper left, upper right, lower left, lower right). In the example, the upper left quadrant is completely homogenous (all areas inside have the value of 0 or 1) while the other quadrants are not; therefore the upper left quadrant can be ignored while the others must be divided further. Non-homogenous quadrants will then be divided further until it each area in the quadrant is homogenous.
In this scenario the reconstruction of the original data would look like this:
The collected data comes in forms of an ID for each area that are homogenous (all areas inside have a value of 0 or 1). They also recorded the original dimension of the area. The ID is recorded as follows:
- The first digit of the ID will be the homogenous value within the quadrant.
- Every following digit represents the location of the current block corresponding to the previous ones. (e.g. if the current block is the upper left quadrant of the previous block then the next digit will be 0.)
Help the team reconstruct the original data with the data they have right now.
* The array size will not exceed 128 * 128 *
** Remember that the dimension of the area must be in the form of 2P*2P for the quadtree structure to work **
Input
The first line contains the number (N) of homogenous areas with the value 1.
The following N lines contain the ID of each area with the homogenous value of 1.
The final line contains the number of number of row and columns in the data.
Output
R lines containing C values of the matrix.
Don't forget to put a newline at the end.
* The last digit of every line must not have a space *
** the last row must not have a new line "