One day, Eloy the byte was walking at the square (1,1) of the big Matrix-shaped city... He was planning to go visit his mom at the square (N,N) when some meteors crashed at the city! Every byte doesn't know what to do... Eloy rapidly discovers that the meteors cause a distortion, multiplying by his hit expansion the streets affected... Eloy knows the matrix and what is contained in it and know the places where the meteor crash, given this, determine the resultant matrix of the city.

 

Additional information: Every street in the initial matrix is filled with ASCII characters from '!' to '}' (from 33 to 125 in ASCII numbers).

The hit expansion for the meteor starts with 5, as it expands will decrease by 1 until arrives to 1, this value will multiply the value of the matrix. This is a example of a hit expansion, (the meteor crashed at the position (3,3))

 

So, in the example of 'c' (position (3,3)) (99 in ASCII) you should multiply it by 5 (495). But in the magic digital world where Eloy lives, this number will be an ASCII symbol. More information on the output.

 

INPUT:

First line of input contains two integers N and K

N Contains the size of the matrix (the matrix will be N^2) (3<=N<=500)

K Contains the number of meteors that crashed in the city. (1<=K<=50)

The next N lines contains N characters separated by a single space, this will be the content of the matrix at position (I,J)

The next K lines contains two integers (Ki and Kj), (Rows,Columns) this two coordinates reveal the position where meteor Kn crashed.

 

OUTPUT:

The output must be the resultant matrix, so, N lines with N characters separated by a single space, as the distortion can get out of range some integers, you must output the ascii value of the number modulo 93 plus 33. That will decrease the number to a range from 33 to 125 as much. This final number must be turned into a character, then print it.

 

SAMPLE:

INPUT:

3 1

a a a

b b b

c c c

2 2

 

OUTPUT:

1 1 1

5 : 5

9 9 9

 

Because:

 

The meteor crash at (2,2) having a starting value of 98, the value in the matrix is modified to 490, then transformed to the range 33~125 giving a result of 58, in ASCII value, 58 represents the “:”.

later, the hit expansion moves to EVERY ADJACENT cell (that means diagonals too) modifying the values inside of it.

 

ANOTHER SAMPLE DATA:

INPUT:

6 1
a a a a a a
b b b b b b
c c c c c c
d d d d d d
e e e e e e
f f f f f f
1 6

OUTPUT:

% % ) - 1 5
& & + 0 5 5
' ' - 3 3 3
( ( / / / /
) ) ) ) ) )
* * * * * *

Please have in consideration that if 2 meteors collide and affects the same zone (cell), the zone with the GREATEST value of modification should be modified.