DISTO - Streets of distortion

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))

Meteor expansion

 

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.


Added by:david_8k
Date:2012-01-06
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:Own problem

hide comments
2021-02-16 21:13:36
In the given 2nd example, why are the a's being converted to %, the b's to &, the c's to '... when their ASCII values don't exceed 125?

Last edit: 2021-02-16 21:15:44
2017-01-18 15:27:56
@don it means that if a cell has multiplier as 2 and due to another meteor strike nearby, its multiplier can become 4, then 4 is to be considered.
2016-05-03 16:28:15 Manuel Acosta
Be careful with spaces in input and output, Great problem to learn.
2014-05-01 18:52:30 Andres R. Arrieche S. [UCLA-ve]
@David Moran My solution 6356057 got AC about 2 years ago, I resubmitted(11507075) but I got TLE. did you add more test cases? if so, I guess you should rejudge all the solutions
2012-07-23 03:10:49 don
"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."
what does this mean cn somebody explain pls...
2012-07-23 03:10:49 Shaily Mittal
Giving correct output for all test cases why still wa.. :(, plese check Submission 7048912
2012-07-23 03:10:49 Himanshu Srivastava
more test case for K>1 PLZ
2012-07-23 03:10:49 Rocker3011
still don´t get why the a´s in the first test case are switch to 1´s and c´s to 9´s /:

David says: Read problem statement

Last edit: 2012-04-01 18:08:01
2012-07-23 03:10:49 Aradhya
move this 2 tutorial.....plzzz..vry easy problem!!!!! :) :) :) :) :)....hahahahaha
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.