/* c11c.c (c11.c) - Don Yang (uguu.org)

   Preprocess 3: Optimize.

   06/02/00
                                                                           */

#include<stdio.h>

int buffer[65536],
    bindex,
    blength,

    run,
    isize, osize,
    isum, osum,
    data,

    code, length, source, i, j;

int input()
{
   isum ^= (data = getchar());
   if( data == EOF )
      isum ^= EOF;
   if( (++isize & 1023) == 0 )
      fputc(46, stderr);
   return data;

}

void output(int bdata)
{
   osize++;
   osum ^= (bdata &= 255);
   putchar(bdata);

}

void bseek(int offset)
{
   for(; offset; offset--)
   {
      bindex = (bindex + 1) & 65535;
      if( !(--blength) )
      {
         buffer[bindex] = input();
         blength++;
      }
   }

}

int bgetc(int offset)
{
   for(; offset >= blength;
      buffer[(bindex + blength++) & 65535] = input());

   return buffer[(bindex + offset + 65536) & 65535];

}

void bflush()
{
   output(run);
   output(run >> 8);

   for(; run; run--)
      output(bgetc(-run));

}

int main(int argc)
{
   for(i = bindex = isize = osize = isum = osum = run = 0;
       i < 65536; buffer[i++] = 0);

   if( argc > 1 )
   {
      for(i = input(); i - EOF; i = input())
      {
         if( (j = input()) == EOF )
            break;

         length = i | (j << 8);
         i = 0;
         if( length & (1<<15) )
         {
            source = length | (-1<<16);

            run = input();
            j = input();
            length = run | (j << 8);

            for(; i < length; i++)
            {
               output(
                  buffer[(bindex + i) % (1<<16)] =
                  buffer[(bindex + i + source + (1<<16)) & 65535]);
            }
         }
         else
         {
            for(; i < length;
               output(buffer[(bindex + i++) & 65535] = input()));
         }
         bindex = (bindex + length) & 65535;
      }

      if( osum ^ i )
         fprintf(stderr, "Checksum failed.\n");
   }

   else
   {
      buffer[0] = input();
      blength = 1;

      for(code = bgetc(0); code - EOF; code = bgetc(0))
      {
         i = 0;
         for( source = -5; source > -32767; source--)
         {
            if( bgetc(source) == code )
            {
               for(length = 1; length < -source; length++)
               {
                  if( bgetc(source + length) - bgetc(length) )
                     break;
               }
               if( length > i )
               {
                  i = length;
                  j = source;
               }
            }
         }

         if( i > 5 )
         {
            if( run )
               bflush();

            output(j);
            output(j >> 8);
            output(i);
            output(i >> 8 );

            bseek(i);
         }
         else
         {
            bseek(1);
            if( ++run > 32766 )
               bflush();
         }
      }

      if( run )
         bflush();

      output(isum);
   }

   isize--;
   return fprintf(stderr, "\n%d/%d\n", osize, isize);
}