Algorithms and Data Structures

Compress the image

The company you currently work for has a huge dataset of black-and-white images. They take up too much space, so the company asks you to implement a compression algorithm to save up space.
Given an image that consists of black and white pixels (blacks are represented as 0s and whites are represented as 1s), you are asked to perform a hierarchical compression by K%.
When applying a hierarchical compression, the algorithm starts from the whole image, then splits the image into 4 equal parts (top-left, top-right, bottom-left, and bottom-right), then splits each of the parts again into 4 equal parts, then does the same for the resulting parts, and so on. If the current part of the image is dominated by a single color, then the algorithm fills the whole part with that color and stops the splitting process there. We say the part is dominated by a single color if it forms ≥ K% of the part.
Given the initial image, your task is to output the compressed one.

Input

The first line of the input contains two integers N (1 ≤ N ≤ 64) and K (51 ≤ K ≤ 100). N is guaranteed to be a power of 2.
The next N lines contain N 0s or 1s.

Output

The program should output the compressed image.

Examples

Input
8 75
11111000
11110000
11000011
11000011
11000100
00000100
00010011
00010011
Output
11110000
11110000
11110011
11110011
00000100
00000100
00000011
00000011

Explanation

Input
Input
 
Output
Output
 

Constraints

Time limit: 2 seconds

Memory limit: 512 MB

Output limit: 1 MB

To check your solution you need to sign in
Sign in to continue