Run-Length Encoding

RLE or "run-length encoding" is one of the simplest data compression methods. It replaces sequence of identical elements with single mentioning of such element and repeat count. Regard an example - let's use digits before letters to specify repetitions:

ZOOOPHTALMOLOGIST   becomes   Z3OPHTALMOLOGIST

BOOKKEEPER   becomes   B2O2K2EPER

Not very impressive! In the first case we only saved 1 symbol, in the second we saved nothing at all. And we need a way to encode numbers somehow - for example we can prepend real digits with redundant repeat count of 1, unless there are repeating digits.

HAL-9000   becomes   HAL-1930

AREA-51   becomes   AREA-1511

Well, that looks silly - and that's why RLE is not general method. It is still very useful in certain special cases. For example we can compress spaces in program source:

# source
n = int(input())
for i in range(n):
    if i % 3 == 0:
        print("fizz")

# compressed
# source
n = int(input())
for i in range(n):
4 if i % 13 == 10:
8 print("fizz")

However the most popular usage for RLE is for encoding images - not images of any type, of course, since common photograph with 16.7 mln colors would rarely have sequences of exactly identical pixels - but rather various drawings, which may have regions and lines of same color.

Especially nice situation happens with monochrome images - here every pixel is represented by single bit, and we need to encode sequences of bits. In this case we can only use repeat counts, but drop off bit values themselves, because we understand that after sequence of white pixels follows sequence of black pixels and vice versa. Let's try an example of image represented with pseudographics:

- X - - X - - - X X X - - X - - - -         112133214
- X - - X - - X - - X - - X - - - -         11212121214
- X X X X - - X - - X - - X - - - -         142121214
- X - - X - - X X X X - - X - - X -         11212421211
- X - - X - - X - - X - - X X X X -         11212121241
- - - - - - - - - - - - - - - - - -         909

Here we encode small image with text HAL, suppose that white dots are marked with "X" and black with "-". Encoding assumes that every line starts with black pixel. First line starts with 1 black, followed by 1 white, then 2 blacks, 1 white, 3 blacks, 3 whites and so on - that's how we get 112133....

What to do if the sequence is of more than 9 pixels? Look at the last line - we encode 18 black pixels as two sequences of 9 with 0 white dots between them. The same approach may be used if line starts with white pixel (in this case its encoded version starts with 0 black).

This is not real improvement yet, since single pixel takes 1 bit but single digit takes 4 bits. Thus we'd better use octal or even ternary digits for this case, to achieve real profit. However real images may be expected to have larger "streaks" of same color and better compression rate.

Problem Statement

The input contains some graphical data encoded as described above, with hexadecimal digits (so bit sequences from 0 to 15 pixels could be encoded). Your task is to decode these data and output them in the same hexadecimal form. I.e. regarding output as bit-stream, every 4 decoded bits (or pixels) are represented by hexadecimal digit, first bit corresponding to least significant of the four.

Answer will be automatically rendered in small graphical field below. You should be able to read code word here. Add this code word to your answer, at the very beginning, separating from everything else with newline. Then submit - that's all!

Input shall provide integers W and H in the first line - width and height of the encoded image.
Next Hlines shall follow each encoded separately.

Answer is expected to contain code word first, then H lines of hexadecimal digits, describing bit data of the image. Each line is going to have W/4 digits obviously.

Example (partial):

Continuing with small "image" shown above, the first line of input is 112133214, answer starts with code word HAL and the first line of the answer is 21720.

Well, example has image 18 pixels wide, not evenly divisible by 4, but never mind - real input shall always have fine dimensions - moreover, always the same. The font used has some letters looking fancy - especially be careful to distingquish Q from O.