## Mock CCC14S3 - Spreadsheet Sorting

View as PDF

Points: 7
Time limit: 1.0s
Memory limit: 16M

Author:
Problem type
##### 2014 Mock CCC by Alex and Timothy

Over the years, Alice has collected the physical data of her friend and secret love interest, Bob. Now she's trying to find trends in the data so she can learn more about Bob, and thus get closer to him. Alice entered the data into her spreadsheet software, but learned that unfortunately, the software doesn't work as it should. Namely, the "sort by column" function is broken. Each time Alice clicks a column, she wants all the rows in the spreadsheet to be sorted in nondecreasing order by values from that column. If rows have the same values in the column she clicks, the relative order of these rows should be preserved after the sort. Given the original spreadsheet and the sequence of the columns that Alice clicked, you are to determine the sorted spreadsheet.

#### Input Specification

Line of input contains two integers: , the number of rows in the spreadsheet, and , the number of columns in the spreadsheet .
The next lines will each contain integers between and inclusive, representing single cells of the spreadsheet.
The next line of input will have an integer , the number of sort commands that Alice makes.
The last lines will each contain a number , indicating that she sorts by column for the -th command .

#### Output Specification

The output should contain lines with integers per line, the sorted spreadsheet after the clicks.

#### Sample Input

4 3
6 2 1
9 1 3
9 2 1
6 1 1
2
2
1

#### Sample Output

6 1 1
6 2 1
9 1 3
9 2 1

#### Explanation

Alice first sorts by column , then she sorts by column . The spreadsheet is sorted as follows:

Before sorting:    Sort by col 2:     Sort by col 1:
6 2 1              9 1 3              6 1 1
9 1 3     ---->    6 1 1     ---->    6 2 1
9 2 1              6 2 1              9 1 3
6 1 1              9 2 1              9 2 1