Сжатие изображения
В компании, в которой вы сейчас работаете, есть огромный набор черно-белых изображений. Они занимают слишком много места, поэтому компания попросила вас реализовать алгоритм сжатия, чтобы сократить объем хранимых данных.
Дано изображение размером , состоящее из белых и черных пикселей (черный обозначается 0, белый обозначается 1). Требуется выполнить иерархическое сжатие на
K%.При иерархическом сжатии алгоритм сначала рассматривает все изображение целиком, затем делит его на 4 равные части (левый верх, правый верх, левый низ и правый низ), потом берет каждую из полученных частей и снова делит на 4 равные части, и так далее. Если в текущей части (блоке) преобладает один цвет, алгоритм полностью заполняет этот блок этим цветом и останавливает дальнейшее разбиение. Мы говорим, что блок «достигает преобладания одного цвета», если этот цвет занимает
≥ K% данной части изображения.Ваша задача — вывести сжатое изображение, исходя из первоначального.
Входные данные
В первой строке входных данных заданы два числа
N (1 ≤ N ≤ 64) и K (51 ≤ K ≤ 100). Гарантируется, что N является степенью двойки.В следующих
N строках содержится по N символов 0 или 1.Выходные данные
Программа должна вывести сжатое изображение.
Примеры
Input
8 75
11111000
11110000
11000011
11000011
11000100
00000100
00010011
00010011Output
11110000
11110000
11110011
11110011
00000100
00000100
00000011
00000011Пояснение
Constraints
Time limit: 1 seconds
Memory limit: 512 MB
Output limit: 1 MB