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):
ABCDEFG
HIJKLMN
OPQRSTU
VWXYZab
cdefghi
jklmnop
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:
ACEG
OQSU
cegi
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:
ADG
VYb
Observe that when , the downsampled image retains only pixels.
Task
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.
Input Format
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.
Scoring
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.
Output Format
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.
Sample Input
3 3 2
6 6
0,0,200 0,0,10 10,0,0
90,90,50 90,90,10 255,255,255
100,100,88 80,80,80 15,75,255
The downsampled image is pixels, with a sampling coefficient of . You must upsample this image and generate an interpolated image of pixels.
The image described above is represented by pixels. The Blue, Green, and Red values provided for each pixel are comma-separated, and the pixel descriptions are space-separated.
The top-left pixel is defined as .
The top-right pixel is defined as .
The bottom-right pixel is defined as .
The bottom-left pixel is defined as .
Sample Output
0,0,200 100,100,100 0,0,10 5,5,5 10,0,0 50,50,50
90,90,50 90,90,50 90,90,10 90,90,10 255,255,255 0,0,10
100,100,88 100,100,88 80,80,80 80,80,80 15,75,255 15,75,255
100,100,88 100,100,88 80,80,80 80,80,80 15,75,255 15,75,255
100,100,88 100,100,88 80,80,80 80,80,80 15,75,255 15,75,255
90,90,50 90,90,50 90,90,10 90,90,10 255,255,255 0,0,10
This is for the purpose of explanation only. We have generated an image of size from the input image.