DPCM Encoding

Time Limit: 1 Second    Memory Limit: 32768 KB

One of the widely-used technologies in voice signal compression is DPCM encoding. The algorithm is very simple, yet it's quite effective in signal transferring.

Given the original voice signals: a1, a2, a3, a4, ..., an, you are supposed to calculate the compressed data bi according to the following equations:

with the initial condition: a0 = b0 = 0, where ai is an 8-bit unsigned integer and bi is a 4-bit signed integer, the highest bit is used to represent its sign.

By applying this method one can successfully achieve 50% compression ratio. Now you are asked to implement this algorithm - please keep in mind that this is going to be used in a real-time system, so your program should be efficient enough to process 64kb data every second.

Input

The input consists of several cases, each starts with an even number n (n <= 10000), indicating the number of the bytes to be processed, then followed by n bytes in hex form.

The input is ended by EOF.

Output

For each test case, output the number of bytes in DPCM in a line, then output the n bytes in hex form, with 8 numbers per line.

Sample Input

6
01 FF 09 07 06 FE
12
FD 00 09 F8 02 03 00 01
02 0B FA 08

Sample Output

3
17 1e f7
6
79 77 8d d1 17 78

Submit

Source: ZOJ Monthly, February 2003