2014 Mock CCC by Alex and Timothy

Problem S3: Spreadsheet Sorting

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 Format

Line 1 of input contains two integers: R, the number of rows in the spreadsheet, and C, the number of columns in the spreadsheet (1 ≤ R, C ≤ 100).
The next R lines will each contain C integers between 1 and 10 000 inclusive, representing single cells of the spreadsheet.
The next line of input will have an integer N (1 ≤ N ≤ 100), the number of sort commands that Alice makes.
The last N lines will each contain a number ci (1 ≤ ciC), indicating that she sorts by column ci for the i-th command (1 ≤ iN).

Output Format

The output should contain R lines with C integers per line, the sorted spreadsheet after the N 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 2, then she sorts by column 1. 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

All Submissions
Best Solutions


Point Value: 7
Time Limit: 2.00s
Memory Limit: 16M
Added: Feb 27, 2014
Author: Alex

Languages Allowed:
C++03, PAS, C, HASK, ASM, RUBY, PYTH2, JAVA, PHP, SCM, CAML, PERL, C#, C++11, PYTH3

Comments (Search)

It's quiet in here...