Третий открытый Зеленоградский турнир 2007

Цифровая обработка

Одна из интереснейших, актуальнейших и сложнейших задач сегодняшнего времени это задача обработки цифровых изображений. Особенно важна такая система в цифровых фотоаппаратах. Дан набор картинок, каждая из которых, представляет собой изображаение в серых тонах (gray scale). Каждая из таких картинок получилась в результате пересылки через ненадежные аналоговые системы передачи данных и в процессе была испорчена точечными помехами. Картинка задается прямоугольной матрицей целых значений от 0 (черный цвет) до 255 (белый цвет). Число X в позиции (i, j) означает, что пиксель на картинке в точке скоординатами x = i, y = j имеет цвет RGB(X, X, X).

Тестовые данные были сгененрированы автоматически из набора картинок (аватар, баннеров, фотографий) найденных в интернете. Затем картинки были пропущены через генератор шума. Генератор шума это функция берущая подряд каждый пиксел изображения и с вероятностью от 2 до 20% заменяющая цвет пиксела на новое значение. Значение выбирается из промежутка [0; 255] с равной вероятностью.

Оригинальная картинка Картинка в серых тонах Картинка после передачи Картинка после работы
программы восстановления
Оригинальная картинка Картинка в серых тонах Картинка после передачи Картинка после работы программы восстановления

Ваша задача по заданной шумной картинке как можно точнее восстановить оригинал. Чем точнее будет ваш рисунок тем меньше штрафных баллов вы получите.

Input

t – число тестов [t <= 60] (общее число тестов не более 250), затем следуют t тестовых последовательностей.
Каждая тестовая последовательность начинается с трех чисел Q, H и W процент шума, высоты и ширины картинки соответственно [2 <= Q <= 20], [10 <= H, W <= 200]. Затем следует H рядов по W целых чисел в каждом.

Output

Для каждого теста необходимо вывести картинку после устранения помех в следующем формате: Сначала два числа H и W высота и ширина картинки соответственно. Они должны совпадать с числами которые были заданы во входной последовательности. Затем должно следовать H рядов по W целых чисел в каждом со значениями цвета восстановленной картинки.

Score

Количество очков за программу равно сумме очков полученных вашей программой за каждый из тестов в отдельности + 1. Количество очков за отдельный тест расчитывается по формуле:
score = sqrt((x[1][1]1 - x[1][1]2)^2 + (x[1][2]1 - x[1][2]2)^2 + .... + (x[H][W]1-x[H][W]2)^2),
где x[i][j]1 - цвет пикселя в позиции i, j на восстановленной картинке
а x[i][j]2 - цвет пикселя в позиции i, j на оригинальной картинке.

Example

Input:
1
6 20 20
 255 255 255 255 255 255 255 255 255 255 255 255 255 255 255 255 255 028 255 255
 255 255 200 255 255 255 255 255 255 255 255 255 255 255 255 255 255 255 255 255
 255 000 255 255 096 255 079 079 079 079 255 045 255 045 255 068 043 043 043 255
 255 000 255 255 096 255 079 255 255 255 255 045 129 045 255 068 255 255 043 255
 255 000 255 255 096 255 079 255 255 255 255 045 255 045 255 068 255 255 189 255
 255 058 058 058 096 255 079 079 079 079 255 045 255 045 255 068 255 255 068 255
 255 076 255 255 096 255 079 255 255 255 255 185 255 045 255 068 255 255 068 255
 255 000 255 255 096 255 079 255 242 255 255 045 255 045 255 068 255 255 068 255
 255 000 255 255 096 255 079 079 079 079 255 045 255 043 255 048 048 048 048 255
 255 255 255 255 255 255 255 255 058 255 255 255 198 255 255 255 255 255 255 255
 036 255 255 255 255 255 255 255 255 255 255 255 255 255 255 255 255 255 255 255
 255 255 100 195 002 167 002 002 002 002 002 002 002 002 002 002 255 255 255 255
 255 255 255 255 002 002 002 002 002 002 002 002 002 002 002 088 255 255 255 255
 255 255 255 255 002 002 002 002 002 002 046 002 002 002 002 002 255 255 143 255
 255 255 255 255 002 002 002 002 002 013 002 002 002 002 002 002 255 255 255 255
 255 255 177 255 255 255 255 104 255 255 255 255 255 255 255 255 012 133 255 255
 022 022 022 022 066 022 022 022 022 022 022 022 022 022 022 022 022 022 022 022
 255 255 255 255 255 255 255 255 255 255 255 255 255 255 255 255 255 255 255 255
 255 255 255 079 079 079 079 079 079 079 079 079 079 079 079 079 079 255 255 255
 255 255 255 255 255 255 255 255 255 255 255 255 255 255 255 255 255 203 255 255

Output:
20 20
 253 253 255 255 255 255 255 255 255 255 255 255 255 255 255 255 255 255 255 255
 254 255 255 255 255 255 255 255 255 255 255 255 255 255 255 255 255 255 255 255
 255 000 255 255 096 255 079 079 079 079 255 045 255 045 255 068 043 043 043 255
 255 000 255 255 096 255 079 255 255 255 255 045 255 045 255 068 255 255 043 255
 255 000 255 255 096 255 079 255 255 255 255 045 255 045 255 068 255 255 043 255
 255 058 058 058 096 255 079 079 079 079 255 045 255 045 255 068 255 255 068 255
 255 000 255 255 096 255 079 255 255 255 255 045 255 045 255 068 255 255 068 255
 255 000 255 255 096 255 079 255 255 255 255 045 255 045 255 068 255 255 068 255
 255 000 255 255 096 255 079 079 079 079 255 045 255 043 255 048 048 048 048 255
 255 255 255 255 255 255 255 255 255 255 255 255 255 255 255 255 255 255 255 255
 255 255 255 255 255 255 255 255 255 255 255 255 255 255 255 255 255 255 255 255
 255 255 255 255 002 002 002 002 002 002 002 002 002 002 002 002 255 255 255 255
 255 255 255 255 002 002 002 002 002 002 002 002 002 002 002 002 255 255 255 255
 255 255 255 255 002 002 002 002 002 002 002 002 002 002 002 002 255 255 255 255
 255 255 255 255 002 002 002 002 002 002 002 002 002 002 002 002 255 255 255 255
 255 255 255 255 255 255 255 255 255 255 255 255 255 255 255 255 255 255 255 255
 022 022 022 022 022 022 022 022 022 022 022 022 022 022 022 022 022 022 022 022
 255 255 255 255 255 255 255 255 255 255 255 255 255 255 255 255 255 255 255 255
 255 255 255 079 079 079 079 079 079 079 079 079 079 079 079 079 079 255 255 255
 255 255 255 255 255 255 255 255 255 255 255 255 255 255 255 255 255 255 255 255

Score:
Оригинальная картинка:
20 20
 255 255 255 255 255 255 255 255 255 255 255 255 255 255 255 255 255 255 255 255
 255 255 255 255 255 255 255 255 255 255 255 255 255 255 255 255 255 255 255 255
 255 000 255 255 096 255 079 079 079 079 255 045 255 045 255 068 043 043 043 255
 255 000 255 255 096 255 079 255 255 255 255 045 255 045 255 068 255 255 043 255
 255 000 255 255 096 255 079 255 255 255 255 045 255 045 255 068 255 255 043 255
 255 058 058 058 096 255 079 079 079 079 255 045 255 045 255 068 255 255 068 255
 255 000 255 255 096 255 079 255 255 255 255 045 255 045 255 068 255 255 068 255
 255 000 255 255 096 255 079 255 255 255 255 045 255 045 255 068 255 255 068 255
 255 000 255 255 096 255 079 079 079 079 255 045 255 043 255 048 048 048 048 255
 255 255 255 255 255 255 255 255 255 255 255 255 255 255 255 255 255 255 255 255
 255 255 255 255 255 255 255 255 255 255 255 255 255 255 255 255 255 255 255 255
 255 255 255 255 002 002 002 002 002 002 002 002 002 002 002 002 255 255 255 255
 255 255 255 255 002 002 002 002 002 002 002 002 002 002 002 002 255 255 255 255
 255 255 255 255 002 002 002 002 002 002 002 002 002 002 002 002 255 255 255 255
 255 255 255 255 002 002 002 002 002 002 002 002 002 002 002 002 255 255 255 255
 255 255 255 255 255 255 255 255 255 255 255 255 255 255 255 255 255 255 255 255
 022 022 022 022 022 022 022 022 022 022 022 022 022 022 022 022 022 022 022 022
 255 255 255 255 255 255 255 255 255 255 255 255 255 255 255 255 255 255 255 255
 255 255 255 079 079 079 079 079 079 079 079 079 079 079 079 079 079 255 255 255
 255 255 255 255 255 255 255 255 255 255 255 255 255 255 255 255 255 255 255 255

score = sqrt(2^2 + 2^2 + 1^2) + 1 = 1 + 3 = 4 (отличие трех чисел в левом верхнем углу)

Оригинальная картинка: 
Зашумленная картинка: