Mr Monk is a detective who has Obsessive Compulsive Disorder (OCD). He cannot stand if there is something untidy. He has to put them in order.

Question: Now, he wants to put the numbers in a 2D array in order. But there are k cells which he cannot move. Help him and put the numbers in order whitout moving the cells in the given positions.

Input specification: Firstly, you will be given two integers (n and m) size of 2D array. Then, you will be given m integers in the following n lines. Next line, you will be given an integer (k): the number of blocked cells. In the following k lines you will be given the (x,y) coordinates of k numbers where 1 ≤ (n and m) ≤ 100; 1 ≤ k ≤ 10,000; and the numbers in the matrix are less 10,001

Output specification: Show the new sorted matrix (sorted matrix including the blocked cells).