#include<assert.h>
#include<stdio.h>

#define BUFFER_SIZE    0x20000

/* Indices to input ring buffer. */
static int m = 0x1ffff, f, e, r,

/* Ring buffer of output code offsets (measured in number of instructions). */
   l[BUFFER_SIZE],

/* Ring buffer of runtime stack sizes. */
   I[BUFFER_SIZE],

/* Output code size (number of instructions). */
   n,

/* Number of already-encoded bytes that are available for matching. */
   t,

/* Offset of matched substring that will be referenced to replace
   buffered bytes.                                                */
   X, x,

/* Offset of code that will generate the matched substring. */
   Y, y,

/* Number of bytes in longest match. */
   Z,

/* Number of bytes from start of matched string that overlaps with
   start of input string.                                          */
   p,

/* Number of bytes from start of match to current cursor position. */
   q,

   i, z;

/* Define a single header dictionary entry. */
#define D(d) ,#d

/* Header text:
   - Uppercase letters causes a dictionary entry to be expanded recursively.
   - Tilde (~) causes the next letter to be copied as is.
   - Everything else is copied as is.                                        */
static char *h[] =
{
/*M*/ ",",
/*N*/ "Pzoltraak"
/*O*/
D(
ZifWU<stdio.h>U<S.h>
Qjmp_bufPj;XmMIMi=1MlMk[999]={1<<30}M*o=k;
Xmain(XdMchar**a){switch(S(j)){default:Yi;I=14;
VP_P__LI~NE__VPpPT(I=_+1)VPqP(i=3M--R(jM*o--)):VNPcaseP_:i%2?YiMp:(_-4)
%9?T(m|=1<<(_-I)):_-I-17?(putchar(m^32)MY*o)?p:q(l=m%256+3Mm=m/512+3Mi)
?(*o-=l)>0?m=i=0Mp:q((o[2]=*o<l?*o:l)M*++o=I-(i=1)M++R(jM_-m*9));
UP__FILE__QZuWVNQ}
returnP0;}QZendifQ
),
/*P*/ "~ ",
/*Q*/ "~\n"
/*R*/ D(oMlongjmp)
/*S*/ D(setjmp)
/*T*/ D((void))
/*U*/ D(QZinclude)
/*V*/ D(QZdefine)
/*W*/ D(ndefN)
/*X*/ D(intP)
/*Y*/ D(m=0M--),
/*Z*/ "#"
},

/* Ring buffer of input bytes. */
   j[BUFFER_SIZE];

/* Expand header to stdout. */
static void B(char *a)
{
   for(; (i = *a); a++)
      if( i > 32 )
         i > 76 && i < 91 ? B(h[i - 77])
                          : (void)putchar(i - 126 ? i : *++a);
}

/* Count number of bits in a 8-bit value. */
static int b(int a)
{
   assert(a >= 0);
   assert(a < 256);
   return a ? a % 2 + b(a / 2) : 0;
}

int main(int a, char **A)
{
   for(B(h[2]);;)
   {
      /* Fill ring buffer with enough bytes for the encoding process to
         consume, without overwriting old history entries.              */
      while( r - e < m / 2 && (i = getchar()) - EOF )
         j[r++ & m] = i;
      if( e == r )
         break;
      assert(f <= e);
      assert(e <= r);

      /* Expire old code entries that are too far away to be matched. */
      while( f < e && ((i = l[f & m]) < 0 || n - i > 256) )
      {
         f++;
      }

      /* Match input against already-encoded bytes. */
      t = e - f;
      assert(t >= 0);
      Z = -1;
      for(i = 0; i < t; i++)
         /* Do not match against regions that was covered by repeat
            code, since there is no address to branch to.           */
         if( (y = l[(x = f + i) & m]) >= 0 )
         {
            for(z = 0;
                /* Verify that length can still be encoded. */
                z < 258 &&
                /* Verify that we are only matching against what's been read. */
                e + z < r &&
                /* Verify that historical substring matches incoming string. */
                j[(x + z) & m] == j[(e + z) & m] &&
                /* Verify that referencing the previous string here will
                   not overflow the runtime stack.                       */
                (
                   (p = x + z - e) < 0
                     ?  /* Matching some string before the current read
                           position.  Stack size is guaranteed to be defined. */
                        I[(x + z) & m]
                     :  /* Matching some string at or after the current read
                           position.  Stack size depends on how many times we
                           have repeated the prefix.                          */
                        (q = e - x,
                         I[(x + p % q) & m] +
                         2 * p / q)
                ) < 998;
                z++)
            {
            }
            if( z > Z || (z == Z && b(n - y - 1) < b(n - Y - 1)) )
               X = x,
               Y = y,
               Z = z;
         }

      if( Z > 2 )
      {
         /* Use previously generated code to cover incoming bytes. */
         assert(Z - 3 >= 0);
         assert(Z - 3 < 256);
         assert(n - Y - 1 >= 0);
         assert(n - Y - 1 < 256);

         /* Advance ring buffer past encoded region.

            Also record address for start of region so that it can be
            used for future matches, while removing addresses for all
            subsequent bytes.                                         */
         for(i = 0; i < Z; l[z] = i++ > 0 ? -1 : n)
         {
            I[z = e++ & m] = I[(X + i) & m] + 2;
         }
         z = (Z - 3) |
             ((n - Y - 1) << 9) |
             (1 << 17);
         n += 2;
      }
      else
      {
         /* Did not find a sufficiently long entry in history, output a
            literal byte.                                               */
         l[i = e++ & m] = n++;
         I[i] = 1;
         z = (j[i] & 255) ^ 288;
      }

      /* Output a set of lines. */
      for(; z; z /= 2)
         puts(h[z & 1] + 1);
   }
   return 0;
}