ENG  RUSTimus Online Judge
Online Judge
Online contests
About Online Judge
Frequently asked questions
Site news
Problem set
Submit solution
Judge status
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests

Later is better than never

About     Problems     Submit solution     Judge status     Standings
Contest is over

G. Stampman

Time limit: 1.0 second
Memory limit: 256 MB
According to the new bill (law), for each document instead of a single seal (printing), q identical seals should be placed. This complicates the forgery of documents, and also reduces the level of unemployment, because now every company has to have a huge staff of stampmen!
Nikita got a job as a trainee-stampman and today he got his first task. In front of him lies a document which has the size n × m. Nikita mentally divided it into n · m identical squares. Nikita also has a seal whose matrix has the size a × b and it is divided into a · b identical squares. Each square of the matrix is either black or colorless, which means that it doesn’t leave any traces on the paper.
Let’s describe the square in the document or in the stamp matrix by a pair of numbers (x, y)—the row number and the column number, where the rows are numbered from top to bottom starting with one, and the columns are numbered from left to right starting with one. Nikita can perform the stamp operation (x, y), which means to put together the upper left square of the stamp matrix with the square (x, y) of the document and press the stamp. After that, all the black squares of the matrix will color the underlying squares of the document. During the stamp operation, the matrix must be entirely within the bounds of the document.
Nikita made q stamp operations (xi, yi). The task would have been done, but everything is not so simple. Let's say that a square is repainted if it has been colored more than once. According to the company rule, a document which contains at least k repainted squares is considered as illegible. Note that a square, that has been painted three or more times, is still counted as one repainted square. Determine the number of stamp operations, after which the document has become illegible, or output the final form of the document.


The first line contains integers n, m and k (1 ≤ n, m ≤ 1000; 1 ≤ k ≤ 100) that are height, width of the document and the minimal unacceptable number of repainted squares, respectively.
The second line contains the integers a and b (1 ≤ an; 1 ≤ bm) that are the height and width of the stamp matrix, respectively.
The following a lines describe the stamp matrix. Each of these lines consists of b characters “.” or “#”. The “.” character is a colorless square, and the “#” character is a black square.
In the following line there is an integer q (1 ≤ q ≤ 105) that is the number of stamp operations.
The following q lines describe operations. Each of them is specified by integers x and y (1 ≤ xna + 1; 1 ≤ ymb + 1) that are the row number and column number, respectively.


If there is a stamp operation, after which the document becomes illegible, in the single line print “Wasted after stamp #s”, where s is the operation number. The stamp operations are numbered from one in the order of description.
Otherwise, output the description of the document after performing all operations. The description consists of n lines of m characters in each, the document description specification is the same as the stamp matrix description specification.


4 3 2
3 2
1 1
2 2
4 3 1
3 2
1 1
2 2
Wasted after stamp #2
Problem Author: Kirill Borozdin
Problem Source: "Later is better than never" Contest
To submit the solution for this problem go to the Problem set: 2134. Stampman