To reduce the size of a -dimensional image, , containing rows and columns of pixels, the image is downsampled using a crude algorithm.
The downsampling algorithm begins sampling from the top-left pixel position, , of the original image and then proceeds to retain only those pixels which are located in those positions where both the row number and the column number are either 0, or integer multiples of some integer . The downsampled image only contains rows and columns where these values correspond to and
Let's assume for a moment that the original image is as follows (where each character indicates a pixel):
This image has rows and columns.
Assume that the pixel is the one positioned at .
If we downsample this image using , we only retain those pixels located in positions where both the row and column numbers are even. This means the downsampled image will be:
Observe that when , the downsampled image retains over a quarter of the pixels.
Now, if we downsample this image using , we only retain those pixels located in positions where both the row and column numbers are multiples of . This means the downsampled image will be:
Observe that when , the downsampled image retains only pixels.
You are provided with the values for a downsampled image and the downsampling coefficient (). Given the size of the original image (and assuming that the algorithm used for downsampling is the one described above), restore the original image using the interpolation or upsampling algorithm of your choice.
The first line contains space-separated integers, (the number of rows in the downsampled image), (the number of columns in the downsampled image) and (the downsample coefficient), respectively.
The second line contains space-separated integers, and , representing the respective numbers of rows and columns in the original image.
The subsequent lines describe the grid representing the pixel-wise values from the images (which were originally in JPG or PNG formats).
Each line contains pixels, and each pixel is represented by three comma-separated values in the range from to denoting the respective Blue, Green, and Red components. There is a space between successive pixels in the same row.
No input test case will exceed 3MB in size. This is the size of the RGB test matrix, NOT the original image from which it was generated.
We define the between an expected pixel value and an estimated pixel value to be:
For each test image, we compute (the mean distance between the actual pixel value and the estimated value) for each pixel position in the image.
The score awarded for an image is . This means that you will receive no score for a test if your mean from the actual image exceeds . Your final score is the average of the awarded scores for each test image.
You may make no more than 15 submissions for this problem, during the contest.
Print a grid of pixel values describing the upsampled image. Your output should follow the same format as the grid received as input.
Note: You should only print the grid; there is no need to specify the number of rows and columns here.