Welcome to ZOJ
Information
Select Problem
Runs
Ranklist
ZOJ Problem Set - 1493
DPCM Encoding

Time Limit: 2 Seconds      Memory Limit: 65536 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



Author: TANG, Jiqing
Source: ZOJ Monthly, February 2003
Submit    Status