You are given an image composed of N⨯M RGB pixels, represented using hexadecimal notation (e.g. #FF0000 for red).

A pixel may be represented using the shorthand hexadecimal form if it has two identical digits representing its red, green and blue components, respectively. For instance, #AABBCC can be compressed down to #ABC, while #AABBCD is not compressible.

Your task is to transform some (possibly none, possibly all) of the pixels in the input image, such that all of the pixels are compressible, and the resulting image resembles the original one as closely as possible.

The difference between two pixels (R, G, B) and (R', G', B') is defined as |R-R'| + |G-G'| + |B-B'|. The difference between two images is defined as the sum of differences of all pairs of homologous pixels. The lower the difference between two images, the more they resemble each other. If a pixel can be compressed in multiple ways that yield the same minimum difference, the lexicographically lower option is preferred.


The first line of input contains two space-separated values: N and M.
Each of the following N lines contains M space-separated pixels, represented using hexadecimal notation.


The output should contain N lines of M space-separated pixels, each. All pixels should be represented using shorthand hexadecimal notation.


  • N * M ≤ 20 000


2 3
#2F0000 #FBDCEA #FF0000
#FFF #ACE #103
#300 #FDE #F00

Sponsors Gold