HDTV

(1995 ACS Problem B)

A solution for this problem can be found here.

The standards for digital High Definition Television (HDTV) currently being developed use many forms of compression to eliminate redundant information and so reduce the amount of data that has to be transmitted.

This problem is a simple simulation of an HDTV decompressor that reconstructs television pictures from command sequences. For simplicity, the pictures are represented by a rectangular array of pixels with the origin (0,0) at the bottom left-hand corner. Each pixel takes on one of the 26 values from A to Z.

INPUT

The system's commands take the form of a single lower-case letter followed by a list of parameters dependent on the command. Many of the parameters refer to rectangular blocks within the picture. In the following list of commands and their parameters, the block (x,y,w,h) is the rectangular block with its bottom left-hand corner at (x,y) and its top right-hand corner at (x+w-1,y+h-1). These commands and their parameters are:

i x y

Initialise a new picture that is x pixels wide and y pixels high. The picture contains no more than 10000 pixels, and the pixels are initialised to the letter A. The last command in the input is indicated by a picture with zero size.

f x y w h l

Fill the block (x,y,w,h) with the character l, where l is an upper-case letter.

c x y w h a b

Copy the block (x,y,w,h) to the block (a,b,w,h). These blocks may overlap.

r x y w h data

Read the values of the block (x,y,w,h) from a list of data. The block is filled row-wise starting with the pixel at (x,y). The data consists of wxh upper-case letters.

d x y w h data

Decompress the data into the block (x,y,w,h), as for the r command. The data is stored in a run-length encoded format of number-letter pairs, where the number specifies the number of times the letter has to be repeated. For example, 3A1B10C is AAABCCCCCCCCCC when decompressed.

The commands and their parameters may contain spaces and tabs to be broken over multiple lines, but the digits comprising a number such as 23 will never be split. The parameters are all positive and are such that all block lie entirely within the picture and the data for the r and d commands are the correct length for the block's size.

OUTPUT

Every time an i command is reached, a checksum is calculated for the existing image before the new image is initialised. The checksum is calculated as the modulo-256 sum of ASCII values of the pixels in the picture and printed on a line in the form :

checksum = 127

with a single space before and after the equals sign. No checksum is printed for the very first i command because there is no picture.

The following diagrams show the state of the pictures when each of the checksums in the sample input and sample output were calculated.


					    LOVE
                  AAAAUGHAAA		    LONE
                  BBBBLEAAAA		    LANE
                  BBBBLLLAAA		    LATE
   AA             AAAABLLAAA                HATE

SAMPLE INPUT

i2 1i 10 4f 0 1 6 2 Bd4 0 3
4 1B6L1E1A
1U1G1H i4 5 r 0 4 4 1 L   OVE c 0 4 4
 1 0 3 f 2 3 1 1 N
c 0 3 4 1 0 2 f 1 2 1 1 A c 0 2 4
1 0 1 r 2 1 1 1 T
c 0 1 4 1 0 0 f 0 0 1 1 Hi 0 0

SAMPLE OUTPUT

checksum = 130
checksum = 152
checksum = 204

This problem was Problem B in the 1995 ACS Australian Programming Competition.