// icfp2001.cpp
//
// Big Hack
// Jeremy Sawicki
// jeremys AT mit DOT edu
//
// ICFP 2001 programming contest

#include <stdio.h>
#include <limits.h>
#include <time.h>
#include <stdlib.h>

#define VERBOSE true

#define marginOfError 6

///////////////////////////////////////////////////////////////////////////////

template<class T, int I, int D>
class BigArr
{
public:
   BigArr();
   ~BigArr();
   T &operator[](int idx);

private:
   T *m_index[1 << I];
};

template<class T, int I, int D>
BigArr<T, I, D>::BigArr()
{
   for (int ii = 0; ii < (1 << I); ii++)
   {
      m_index[ii] = 0;
   }
}

template<class T, int I, int D>
BigArr<T, I, D>::~BigArr()
{
   for (int ii = 0; ii < (1 << I); ii++)
   {
      if (m_index[ii])
      {
         delete[] m_index[ii];
      }
   }
}

template<class T, int I, int D>
T &BigArr<T, I, D>::operator[](int idx)
{
   int ii = idx >> D;
   int jj = idx & ((1<<D) - 1);
   if (!m_index[ii])
   {
      m_index[ii] = new T[1 << D];
   }
   return m_index[ii][jj];
}

///////////////////////////////////////////////////////////////////////////////

const int rootSize = 10;
const int rootColor = 8;

const char colorLetters[] = {'r', 'g', 'b', 'c', 'm', 'y', 'k', 'w'};
char invertedColorLetters[128];

void invertColorLetters()
{
   for (int ii = 0; ii < 8; ii++)
   {
      invertedColorLetters[colorLetters[ii]] = ii;
   }
}

///////////////////////////////////////////////////////////////////////////////

class Context
{
public:
   Context() {};
   ~Context() {};
   bool operator==(const Context &other)
   {
      return
         getB() == other.getB() &&
         getI() == other.getI() &&
         getSem() == other.getSem() &&
         getTT() == other.getTT() &&
         getU() == other.getU() &&
         getSize() == other.getSize() &&
         getColor() == other.getColor();
   }

   unsigned int getB() const { return m_bits.m_bitsB; }
   unsigned int getI() const { return m_bits.m_bitsI; }
   unsigned int getSem() const { return m_bits.m_bitsSem; }
   unsigned int getTT() const { return m_bits.m_bitsTT; }
   unsigned int getU() const { return m_bits.m_bitsU; }
   unsigned int getSize() const { return m_bits.m_bitsSize; }
   unsigned int getColor() const { return m_bits.m_bitsColor; }

   void setB(unsigned int b) { m_bits.m_bitsB = b; }
   void setI(unsigned int i) { m_bits.m_bitsI = i; }
   void setSem(unsigned int sem) { m_bits.m_bitsSem = sem; }
   void setTT(unsigned int tt) { m_bits.m_bitsTT = tt; }
   void setU(unsigned int u) { m_bits.m_bitsU = u; }
   void setSize(unsigned int size) { m_bits.m_bitsSize = size; }
   void setColor(unsigned int color) { m_bits.m_bitsColor = color; }

   void setRoot()
   {
      setB(0);
      setI(0);
      setSem(0);
      setTT(0);
      setU(0);
      setSize(rootSize);
      setColor(rootColor);
   }

private:
   struct
   {
      unsigned int m_bitsSize : 4;
      unsigned int m_bitsColor : 4;
      unsigned int m_bitsU : 2;
      unsigned int m_bitsSem : 2;
      unsigned int m_bitsB : 1;
      unsigned int m_bitsI : 1;
      unsigned int m_bitsTT : 1;
   } m_bits;
};

Context makeSpaceContext(Context context)
{
   context.setI(0);
   context.setB(0);
   context.setSem(0);
   if (context.getU() == 0)
   {
      context.setColor(7);
   }
   return context;
}

///////////////////////////////////////////////////////////////////////////////

class StatusItem
{
public:
   StatusItem() {};
   ~StatusItem() {};

   signed char m_lenOffset;
};

class Status
{
public:
   Status() : m_items(0) {}
   ~Status() { if (m_items) { delete[] m_items; } }

   int m_lenBase;
   int m_bestRootLen;
   StatusItem *m_items;
};

///////////////////////////////////////////////////////////////////////////////

typedef BigArr<char, 12, 16> BigCharArr;
typedef BigArr<Context, 12, 16> BigContextArr;
typedef BigArr<Status, 12, 16> BigStatusArr;
typedef BigArr<int, 12, 16> BigIntArr;
typedef BigArr<bool, 12, 16> BigBoolArr;


BigCharArr inFile;
int inFileSize = 0;

int parsedSize = 0;
BigCharArr parsedChars;
BigContextArr parsedContexts;

BigCharArr outFiles[2];
int outFileSizes[2] = {0, 0};
int curOutFile = 0;

int bestSize = INT_MAX;
int bestOutFile = -1;

BigStatusArr statusArr;
BigIntArr collapseIndex;

BigIntArr rootColorCounts;
BigIntArr rootSizeCounts;
BigContextArr initialContextArr;
BigBoolArr initialSpaceArr;

BigIntArr partialLengths;
BigIntArr partialSkips;

time_t endTime;
time_t gapStart;
int longestGap = 0;

bool outOfTime()
{
   time_t currentTime = time(0);

   int newGap = currentTime - gapStart;
   if (newGap > longestGap)
   {
      longestGap = newGap;
   }

   gapStart = currentTime;

   return (endTime - currentTime < longestGap + marginOfError);
}

void readFile()
{
   char buf[1024];
   while (!feof(stdin))
   {
      size_t bytesRead = fread(buf, sizeof(char), sizeof(buf), stdin);
      for (size_t ii = 0; ii < bytesRead; ii++)
      {
         inFile[inFileSize++] = buf[ii];
      }
   }

   /*
   int inCh;
   do {
      inCh = getchar();
      if (inCh != EOF)
      {
         inFile[inFileSize] = inCh;
         inFileSize++;
      }
   } while (inCh != EOF);
   */
}

void writeBigCharArr(BigCharArr &arr, int size)
{
   char buf[1024];

   int ii = 0;
   while (ii < size)
   {
      size_t bytesToWrite;
      if (size - ii > 1024)
      {
         bytesToWrite = 1024;
      }
      else
      {
         bytesToWrite = size - ii;
      }

      for (size_t jj = 0; jj < bytesToWrite; jj++)
      {
         buf[jj] = arr[ii + jj];
      }

      fwrite(buf, sizeof(char), bytesToWrite, stdout);

      ii += bytesToWrite;
   }

   /*
   for (int ii = 0; ii < size; ii++)
   {
      putchar(arr[ii]);
   }
   */
}

void writeInFile()
{
   writeBigCharArr(inFile, inFileSize);
}

void writeParsedChars()
{
   writeBigCharArr(parsedChars, parsedSize);
}

void writeOutFile(int num)
{
   writeBigCharArr(outFiles[num], outFileSizes[num]);
}

void addParsedChar(char ch, Context context)
{
   parsedChars[parsedSize] = ch;
   parsedContexts[parsedSize] = context;
   parsedSize++;
}

void addOutChar(char ch)
{
   outFiles[curOutFile][outFileSizes[curOutFile]] = ch;
   outFileSizes[curOutFile]++;
}

void parseFile()
{
   BigContextArr contextStack;
   int contextStackPtr = 0;

   Context curContext;
   curContext.setRoot();

   int ii = 0;
   while (ii < inFileSize)
   {
      char curChar = inFile[ii];
      ii++;

      switch (curChar)
      {
      case 0x20:
      case 0x0d:
      case 0x0a:
      case 0x09:
         {
            Context curSpaceContext = makeSpaceContext(curContext);
            if (curContext.getTT())
            {
               addParsedChar(curChar, curSpaceContext);
            }
            else
            {
               bool skip = false;
               if (!(parsedSize > 0 &&
                     parsedChars[parsedSize-1] == ' ' &&
                     parsedContexts[parsedSize-1] == curSpaceContext))
               {
                  addParsedChar(' ', curSpaceContext);
               }
            }
         }
         break;
      case '<':
         {
            char tagChar = inFile[ii];
            ii++;

            if (tagChar == '/')
            {
               contextStackPtr--;
               curContext = contextStack[contextStackPtr];
               while(inFile[ii] != '>')
               {
                  ii++;
               }
            }
            else
            {
               contextStack[contextStackPtr] = curContext;
               contextStackPtr++;

               switch (tagChar)
               {
               case 'B':
                  {
                     curContext.setB(1);
                  }
                  break;
               case 'I':
                  {
                     curContext.setI(1);
                  }
                  break;
               case 'T':
                  {
                     curContext.setTT(1);
                     ii++;
                  }
                  break;
               case 'S':
                  {
                     curContext.setSem(2);
                  }
                  break;
               case 'E':
                  {
                     unsigned int sem = curContext.getSem();
                     if (sem != 2)
                     {
                        curContext.setSem(1 - sem);
                     }
                     ii++;
                  }
                  break;
               case 'P':
                  {
                     curContext.setSem(0);
                     curContext.setI(0);
                     curContext.setB(0);
                     curContext.setTT(0);
                     curContext.setU(0);
                     ii++;
                  }
                  break;
               case 'U':
                  {
                     unsigned int u = curContext.getU();
                     if (u < 3)
                     {
                        curContext.setU(u + 1);
                     }
                  }
                  break;
               case '0':
               case '1':
               case '2':
               case '3':
               case '4':
               case '5':
               case '6':
               case '7':
               case '8':
               case '9':
                  {
                     curContext.setSize(tagChar - '0');
                  }
                  break;
               default:
                  {
                     curContext.setColor(invertedColorLetters[tagChar]);
                  }
               }
            }

            // > character
            ii++;
         }
         break;
      default:
         {
            addParsedChar(curChar, curContext);
         }
      }
   }
}

void makeSimpleSolution()
{
   for (int ii = 0; ii < parsedSize; ii++)
   {
      Context context = parsedContexts[ii];
      char ch = parsedChars[ii];

      if (context.getB())
      {
         addOutChar('<');
         addOutChar('B');
         addOutChar('>');
      }

      if (context.getI())
      {
         addOutChar('<');
         addOutChar('I');
         addOutChar('>');
      }

      if (context.getTT())
      {
         addOutChar('<');
         addOutChar('T');
         addOutChar('T');
         addOutChar('>');
      }

      unsigned int jj;
      for (jj = 0; jj < context.getU(); jj++)
      {
         addOutChar('<');
         addOutChar('U');
         addOutChar('>');
      }

      if (context.getSem() == 1)
      {
         addOutChar('<');
         addOutChar('E');
         addOutChar('M');
         addOutChar('>');
      }
      else if (context.getSem() == 2)
      {
         addOutChar('<');
         addOutChar('S');
         addOutChar('>');
      }

      if (context.getSize() != rootSize)
      {
         addOutChar('<');
         addOutChar(context.getSize() + '0');
         addOutChar('>');
      }

      if (context.getColor() != rootColor)
      {
         addOutChar('<');
         addOutChar(colorLetters[context.getColor()]);
         addOutChar('>');
      }

      addOutChar(ch);

      if (context.getColor() != rootColor)
      {
         addOutChar('<');
         addOutChar('/');
         addOutChar(colorLetters[context.getColor()]);
         addOutChar('>');
      }

      if (context.getSize() != rootSize)
      {
         addOutChar('<');
         addOutChar('/');
         addOutChar(context.getSize() + '0');
         addOutChar('>');
      }

      if (context.getSem() == 1)
      {
         addOutChar('<');
         addOutChar('/');
         addOutChar('E');
         addOutChar('M');
         addOutChar('>');
      }
      else if (context.getSem() == 2)
      {
         addOutChar('<');
         addOutChar('/');
         addOutChar('S');
         addOutChar('>');
      }

      for (jj = 0; jj < context.getU(); jj++)
      {
         addOutChar('<');
         addOutChar('/');
         addOutChar('U');
         addOutChar('>');
      }

      if (context.getTT())
      {
         addOutChar('<');
         addOutChar('/');
         addOutChar('T');
         addOutChar('T');
         addOutChar('>');
      }

      if (context.getI())
      {
         addOutChar('<');
         addOutChar('/');
         addOutChar('I');
         addOutChar('>');
      }

      if (context.getB())
      {
         addOutChar('<');
         addOutChar('/');
         addOutChar('B');
         addOutChar('>');
      }

   }
}

int contextDist(Context fromContext, Context toContext)
{
   unsigned int fromSize = fromContext.getSize();
   unsigned int fromColor = fromContext.getColor();
   unsigned int fromB = fromContext.getB();
   unsigned int fromI = fromContext.getI();
   unsigned int fromTT = fromContext.getTT();
   unsigned int fromU = fromContext.getU();
   unsigned int fromSem = fromContext.getSem();

   unsigned int toSize = toContext.getSize();
   unsigned int toColor = toContext.getColor();
   unsigned int toB = toContext.getB();
   unsigned int toI = toContext.getI();
   unsigned int toTT = toContext.getTT();
   unsigned int toU = toContext.getU();
   unsigned int toSem = toContext.getSem();

   if (fromSize != rootSize && toSize == rootSize)
   {
      return -1;
   }

   if (fromColor != rootColor && toColor == rootColor)
   {
      return -1;
   }

   int len = 0;
   if (fromB <= toB &&
       fromI <= toI &&
       fromTT <= toTT &&
       fromU <= toU &&
       (fromSem >> 1) <= (toSem >> 1))
   {
      len =
         7 * ((toB - fromB) +
              (toI - fromI) +
              (toU - fromU)) +
         9 * (toTT - fromTT);
      if (fromSem != toSem)
      {
         if (toSem == 2)
         {
            len += 7;
         }
         else
         {
            len += 9;
         }
      }
   }
   else
   {
      len = 9 +
         7 * (toB +
              toI +
              toU) +
         9 * toTT;
      if (toSem == 1)
      {
         len += 9;
      }
      else if (toSem == 2)
      {
         len += 7;
      }
   }

   if (fromSize != toSize)
   {
      len += 7;
   }
   if (fromColor != toColor)
   {
      len += 7;
   }

   return len;
}

inline int contextDistInline(
   unsigned int fromSize,
   unsigned int fromColor,
   unsigned int fromB,
   unsigned int fromI,
   unsigned int fromTT,
   unsigned int fromU,
   unsigned int fromSem,

   unsigned int toSize,
   unsigned int toColor,
   unsigned int toB,
   unsigned int toI,
   unsigned int toTT,
   unsigned int toU,
   unsigned int toSem)
{
   int len = 0;
   if (fromB <= toB &&
       fromI <= toI &&
       fromTT <= toTT &&
       fromU <= toU &&
       (fromSem >> 1) <= (toSem >> 1))
   {
      len =
         7 * ((toB - fromB) +
              (toI - fromI) +
              (toU - fromU)) +
         9 * (toTT - fromTT);
      if (fromSem != toSem)
      {
         if (toSem == 2)
         {
            len += 7;
         }
         else
         {
            len += 9;
         }
      }
   }
   else
   {
      len = 9 +
         7 * (toB +
              toI +
              toU) +
         9 * toTT;
      if (toSem == 1)
      {
         len += 9;
      }
      else if (toSem == 2)
      {
         len += 7;
      }
   }

   if (fromSize != toSize)
   {
      len += 7;
   }
   if (fromColor != toColor)
   {
      len += 7;
   }

   return len;
}

Context nearestSpaceContext(Context fromContext, Context toContext)
{
   unsigned int fromSize = fromContext.getSize();
   unsigned int fromColor = fromContext.getColor();
   unsigned int fromB = fromContext.getB();
   unsigned int fromI = fromContext.getI();
   unsigned int fromTT = fromContext.getTT();
   unsigned int fromU = fromContext.getU();
   unsigned int fromSem = fromContext.getSem();

   unsigned int toSize = toContext.getSize();
   unsigned int toColor = toContext.getColor();
   unsigned int toB = toContext.getB();
   unsigned int toI = toContext.getI();
   unsigned int toTT = toContext.getTT();
   unsigned int toU = toContext.getU();
   unsigned int toSem = toContext.getSem();

   if (fromSize != rootSize && toSize == rootSize)
   {
      return toContext;
   }

   if (fromColor != rootColor && toColor == rootColor)
   {
      return toContext;
   }

   Context nearestContext = fromContext;

   if (fromTT <= toTT &&
       fromU <= toU)
   {
      nearestContext.setTT(toTT);
      nearestContext.setU(toU);
   }
   else
   {
      nearestContext.setB(0);
      nearestContext.setI(0);
      nearestContext.setSem(0);
      nearestContext.setTT(toTT);
      nearestContext.setU(toU);
   }

   if (fromSize != toSize)
   {
      nearestContext.setSize(toSize);
   }
   if (toU > 0)
   {
      if (fromColor != toColor)
      {
         nearestContext.setColor(toColor);
      }
   }

   return nearestContext;
}

inline unsigned int makeItemIdx(
   bool hasRootSize,
   bool hasRootColor,
   unsigned int b,
   unsigned int i,
   unsigned int tt,
   unsigned int u,
   unsigned int sem,
   unsigned int size,
   unsigned int color)
{
   unsigned int colorSizePiece = 0;
   if (!hasRootColor)
   {
      colorSizePiece += color;
      if (!hasRootSize)
      {
         colorSizePiece *= 11;
      }
   }
   if (!hasRootSize)
   {
      colorSizePiece += size;
   }

   return
      b +
      (i << 1) +
      (tt << 2) +
      (u << 3) +
      ((colorSizePiece * 3 + sem) << 5);
}

bool hasRootColor(int firstChar, int lastChar)
{
   return (rootColorCounts[lastChar + 1] - rootColorCounts[firstChar]) > 0;
}

bool hasRootSize(int firstChar, int lastChar)
{
   return (rootSizeCounts[lastChar + 1] - rootSizeCounts[firstChar]) > 0;
}

bool areCompatible(Context context1, bool space1, Context context2, bool space2)
{
   if (!space1 && !space2)
   {
      return context1 == context2;
   }
   else
   {
      return
         context1.getTT() == context2.getTT() &&
         context1.getU() == context2.getU() &&
         context1.getSize() == context2.getSize() &&
         (context1.getU() == 0 ||
          (context1.getColor() == context2.getColor()));
   }
}

int prepareWork()
{
   rootColorCounts[0] = 0;
   rootSizeCounts[0] = 0;
   collapseIndex[0] = 0;

   int ii = 0;
   int nStatus = 0;
   while (ii < parsedSize)
   {
      char ch = parsedChars[ii];
      bool space = 
         (ch == 0x20 ||
          ch == 0x0d ||
          ch == 0x0a ||
          ch == 0x09);

      Context context = parsedContexts[ii];

      int jj = ii + 1;
      bool compatible = true;
      do
      {
         if (jj < parsedSize)
         {
            char nextCh = parsedChars[jj];
            bool nextSpace = 
               (nextCh == 0x20 ||
                nextCh == 0x0d ||
                nextCh == 0x0a ||
                nextCh == 0x09);
            Context nextContext = parsedContexts[jj];

            if (areCompatible(context, space, nextContext, nextSpace))
            {
               if (space)
               {
                  context = nextContext;
               }
               space = space && nextSpace;
            }
            else
            {
               compatible = false;
            }
         }
         else
         {
            compatible = false;
         }
         if (compatible)
         {
            jj++;
         }
      } while (compatible);

      collapseIndex[nStatus + 1] = jj;

      rootSizeCounts[nStatus + 1] = rootSizeCounts[nStatus];
      bool isRootSize = (context.getSize() == rootSize);
      if (isRootSize)
      {
         rootSizeCounts[nStatus + 1]++;
      }

      rootColorCounts[nStatus + 1] = rootColorCounts[nStatus];
      bool isRootColor = ((!space || context.getU() > 0) && context.getColor() == rootColor);
      if (isRootColor)
      {
         rootColorCounts[nStatus + 1]++;
      }

      initialContextArr[nStatus] = context;
      initialSpaceArr[nStatus] = space;

      nStatus++;
      ii = jj;
   }

   return nStatus;
}

int tri(int n)
{
   return (n * (n + 1)) >> 1;
}

Status &getStatus(int workSize, int numChars, int startChar)
{
   //return statusArr[workSize * (numChars - 1) + startChar];

   return statusArr[tri(workSize) - tri(workSize - (numChars - 1)) + startChar];
}

inline int findBest(int workSize, int numChars, int startChar,
   bool totalHasRootColor,
   bool totalHasRootSize,
   unsigned int fromSize,
   unsigned int fromColor,
   unsigned int fromB,
   unsigned int fromI,
   unsigned int fromTT,
   unsigned int fromU,
   unsigned int fromSem,
   int *pSplitPoint,
   Context *pToContext)
{
   if (numChars == 1)
   {
      Context fromContext;
      fromContext.setB(fromB);
      fromContext.setI(fromI);
      fromContext.setTT(fromTT);
      fromContext.setU(fromU);
      fromContext.setSem(fromSem);
      fromContext.setColor(fromColor);
      fromContext.setSize(fromSize);

      if (initialSpaceArr[startChar])
      {
         Context tempContext = nearestSpaceContext(fromContext, initialContextArr[startChar]);
         if (pToContext)
         {
            *pToContext = tempContext;
         }
         return contextDist(fromContext, tempContext);
      }
      else
      {
         Context tempContext = initialContextArr[startChar];
         if (pToContext)
         {
            *pToContext = tempContext;
         }
         return contextDist(fromContext, tempContext);
      }
   }

   unsigned int highToColor =
      (fromColor == rootColor) ? rootColor : (rootColor - 1);
   unsigned int highToSize =
      (fromSize == rootSize) ? rootSize : (rootSize - 1);

   unsigned int lowToColor =
      (totalHasRootColor) ? rootColor : 0;
   unsigned int lowToSize =
      (totalHasRootSize) ? rootSize : 0;

   int curLen;

#if 0
   {
   curLen = INT_MAX;

   int mm = INT_MAX;
   for (int splitPoint = startChar + 1; splitPoint < (startChar + numChars); splitPoint++)
   {
      Status &status1 = getStatus(workSize, splitPoint - startChar, startChar);
      Status &status2 = getStatus(workSize, numChars - (splitPoint - startChar), splitPoint);

      int sum = status1.m_lenBase + status2.m_lenBase;
      if (sum < mm)
      {
         mm = sum;
      }
   }

   for (unsigned int toB = 0; toB <= 1; toB++)
   {
      for (unsigned int toI = 0; toI <= 1; toI++)
      {
         for (unsigned int toTT = 0; toTT <= 1; toTT++)
         {
            for (unsigned int toU = 0; toU <= 3; toU++)
            {
               for (unsigned int toSem = 0; toSem <= 2; toSem++)
               {
                  for (unsigned int toColor = lowToColor; toColor <= highToColor; toColor++)
                  {
                     for (unsigned int toSize = lowToSize; toSize <= highToSize; toSize++)
                     {
                        int contextSwitchLen = contextDistInline(
                           fromSize,
                           fromColor,
                           fromB,
                           fromI,
                           fromTT,
                           fromU,
                           fromSem,

                           toSize,
                           toColor,
                           toB,
                           toI,
                           toTT,
                           toU,
                           toSem);

                        if (contextSwitchLen + mm < curLen)
                        {
                           for (int splitPoint = startChar + 1; splitPoint < (startChar + numChars); splitPoint++)
                           {

                              Status &status1 = getStatus(workSize, splitPoint - startChar, startChar);
                              Status &status2 = getStatus(workSize, numChars - (splitPoint - startChar), splitPoint);

                              bool half1HasRootColor = hasRootColor(startChar, splitPoint - 1);
                              bool half1HasRootSize = hasRootSize(startChar, splitPoint - 1);
                              bool half2HasRootColor = hasRootColor(splitPoint, startChar + numChars - 1);
                              bool half2HasRootSize = hasRootSize(splitPoint, startChar + numChars - 1);

                              unsigned int half1ItemIdx = makeItemIdx(
                                 half1HasRootSize,
                                 half1HasRootColor,
                                 toB,
                                 toI,
                                 toTT,
                                 toU,
                                 toSem,
                                 toSize,
                                 toColor);
                              unsigned int half2ItemIdx = makeItemIdx(
                                 half2HasRootSize,
                                 half2HasRootColor,
                                 toB,
                                 toI,
                                 toTT,
                                 toU,
                                 toSem,
                                 toSize,
                                 toColor);

                              int halfLen1 = status1.m_lenBase + status1.m_items[half1ItemIdx].m_lenOffset;
                              int halfLen2 = status2.m_lenBase + status2.m_items[half2ItemIdx].m_lenOffset;

                              int totalLen = contextSwitchLen + halfLen1 + halfLen2;

                              if (totalLen < curLen)
                              {
                                 curLen = totalLen;
                                 if (pSplitPoint)
                                 {
                                    *pSplitPoint = splitPoint;

                                    pToContext->setB(toB);
                                    pToContext->setI(toI);
                                    pToContext->setTT(toTT);
                                    pToContext->setU(toU);
                                    pToContext->setSem(toSem);
                                    pToContext->setColor(toColor);
                                    pToContext->setSize(toSize);
                                 }
                              }
                           }

                        }

                     }
                  }
               }
            }
         }
      }
   }
   }
#endif

#if 1
   {
   curLen = INT_MAX;

   for (int splitPoint = startChar + 1; splitPoint < (startChar + numChars); splitPoint++)
   {

      Status &status1 = getStatus(workSize, splitPoint - startChar, startChar);
      Status &status2 = getStatus(workSize, numChars - (splitPoint - startChar), splitPoint);

      bool half1HasRootColor = hasRootColor(startChar, splitPoint - 1);
      bool half1HasRootSize = hasRootSize(startChar, splitPoint - 1);
      bool half2HasRootColor = hasRootColor(splitPoint, startChar + numChars - 1);
      bool half2HasRootSize = hasRootSize(splitPoint, startChar + numChars - 1);

      if (status1.m_lenBase + status2.m_lenBase < curLen)
      {

         for (unsigned int toColor = lowToColor; toColor <= highToColor; toColor++)
         {
            for (unsigned int toSize = lowToSize; toSize <= highToSize; toSize++)
            {
               unsigned int colorSizePiece1 = 0;
               if (!half1HasRootColor)
               {
                  colorSizePiece1 += toColor;
                  if (!half1HasRootSize)
                  {
                     colorSizePiece1 *= 11;
                  }
               }
               if (!half1HasRootSize)
               {
                  colorSizePiece1 += toSize;
               }

               unsigned int colorSizePiece2 = 0;
               if (!half2HasRootColor)
               {
                  colorSizePiece2 += toColor;
                  if (!half2HasRootSize)
                  {
                     colorSizePiece2 *= 11;
                  }
               }
               if (!half2HasRootSize)
               {
                  colorSizePiece2 += toSize;
               }

               colorSizePiece1 *= 96;
               colorSizePiece2 *= 96;

               for (unsigned int toSem = 0; toSem <= 2; toSem++)
               {
                  unsigned int withSem = toSem << 5;

                  for (unsigned int toB = 0; toB <= 1; toB++)
                  {
                     unsigned int withB = withSem | toB;

                     for (unsigned int toI = 0; toI <= 1; toI++)
                     {
                        unsigned int withI = withB | (toI << 1);

                        for (unsigned int toTT = 0; toTT <= 1; toTT++)
                        {
                           unsigned int withTT = withI | (toTT << 2);

                           for (unsigned int toU = 0; toU <= 3; toU++)
                           {
                              unsigned int withU = withTT | (toU << 3);

                              /*
                              unsigned int half1ItemIdx = makeItemIdx(
                                 half1HasRootSize,
                                 half1HasRootColor,
                                 toB,
                                 toI,
                                 toTT,
                                 toU,
                                 toSem,
                                 toSize,
                                 toColor);
                              unsigned int half2ItemIdx = makeItemIdx(
                                 half2HasRootSize,
                                 half2HasRootColor,
                                 toB,
                                 toI,
                                 toTT,
                                 toU,
                                 toSem,
                                 toSize,
                                 toColor);
                              */
                              unsigned int half1ItemIdx = colorSizePiece1 + withU;
                              unsigned int half2ItemIdx = colorSizePiece2 + withU;

                              int halfLen1 = status1.m_lenBase + status1.m_items[half1ItemIdx].m_lenOffset;
                              int halfLen2 = status2.m_lenBase + status2.m_items[half2ItemIdx].m_lenOffset;

                              int totalLen = halfLen1 + halfLen2;

                              if (totalLen < curLen)
                              {
                                 int contextSwitchLen = contextDistInline(
                                    fromSize,
                                    fromColor,
                                    fromB,
                                    fromI,
                                    fromTT,
                                    fromU,
                                    fromSem,

                                    toSize,
                                    toColor,
                                    toB,
                                    toI,
                                    toTT,
                                    toU,
                                    toSem);

                                 totalLen += contextSwitchLen;

                                 if (totalLen < curLen)
                                 {
                                    curLen = totalLen;
                                    if (pSplitPoint)
                                    {
                                       *pSplitPoint = splitPoint;

                                       pToContext->setB(toB);
                                       pToContext->setI(toI);
                                       pToContext->setTT(toTT);
                                       pToContext->setU(toU);
                                       pToContext->setSem(toSem);
                                       pToContext->setColor(toColor);
                                       pToContext->setSize(toSize);
                                    }
                                 }
                              }

                           }
                        }
                     }
                  }
               }
            }
         }

      }

   }
   }
#endif

   return curLen;
}

void makeSolutionAux(int workSize, int numChars, int startChar, Context fromContext)
{
   unsigned int fromSize = fromContext.getSize();
   unsigned int fromColor = fromContext.getColor();
   unsigned int fromB = fromContext.getB();
   unsigned int fromI = fromContext.getI();
   unsigned int fromTT = fromContext.getTT();
   unsigned int fromU = fromContext.getU();
   unsigned int fromSem = fromContext.getSem();

   bool totalHasRootColor = hasRootColor(startChar, startChar + numChars - 1);
   bool totalHasRootSize = hasRootSize(startChar, startChar + numChars - 1);

   int splitPoint = 0;
   Context toContext;

   findBest(workSize, numChars, startChar,
      totalHasRootColor,
      totalHasRootSize,
      fromSize,
      fromColor,
      fromB,
      fromI,
      fromTT,
      fromU,
      fromSem,
      &splitPoint,
      &toContext);

   unsigned int toSize = toContext.getSize();
   unsigned int toColor = toContext.getColor();
   unsigned int toB = toContext.getB();
   unsigned int toI = toContext.getI();
   unsigned int toTT = toContext.getTT();
   unsigned int toU = toContext.getU();
   unsigned int toSem = toContext.getSem();

   unsigned int numPl = 0;
   unsigned int numB = 0;
   unsigned int numI = 0;
   unsigned int numTT = 0;
   unsigned int numU = 0;
   unsigned int numS = 0;
   unsigned int numEm = 0;

   if (fromB <= toB &&
       fromI <= toI &&
       fromTT <= toTT &&
       fromU <= toU &&
       (fromSem >> 1) <= (toSem >> 1))
   {
      numB = toB - fromB;
      numI = toI - fromI;
      numU = toU - fromU;
      numTT = toTT - fromTT;
      if (fromSem != toSem)
      {
         if (toSem == 2)
         {
            numS = 1;
         }
         else
         {
            numEm = 1;
         }
      }
   }
   else
   {
      numPl = 1;
      numB = toB;
      numI = toI;
      numU = toU;
      numTT = toTT;
      if (toSem == 1)
      {
         numEm = 1;
      }
      else if (toSem == 2)
      {
         numS = 1;
      }
   }

   unsigned int ii;

   for (ii = 0; ii < numPl; ii++)
   {
      addOutChar('<');
      addOutChar('P');
      addOutChar('L');
      addOutChar('>');
   }

   for (ii = 0; ii < numB; ii++)
   {
      addOutChar('<');
      addOutChar('B');
      addOutChar('>');
   }

   for (ii = 0; ii < numI; ii++)
   {
      addOutChar('<');
      addOutChar('I');
      addOutChar('>');
   }

   for (ii = 0; ii < numTT; ii++)
   {
      addOutChar('<');
      addOutChar('T');
      addOutChar('T');
      addOutChar('>');
   }

   for (ii = 0; ii < numU; ii++)
   {
      addOutChar('<');
      addOutChar('U');
      addOutChar('>');
   }

   for (ii = 0; ii < numS; ii++)
   {
      addOutChar('<');
      addOutChar('S');
      addOutChar('>');
   }

   for (ii = 0; ii < numEm; ii++)
   {
      addOutChar('<');
      addOutChar('E');
      addOutChar('M');
      addOutChar('>');
   }

   if (fromColor != toColor)
   {
      addOutChar('<');
      addOutChar(colorLetters[toColor]);
      addOutChar('>');
   }

   if (fromSize != toSize)
   {
      addOutChar('<');
      addOutChar(toSize + '0');
      addOutChar('>');
   }

   if (numChars == 1)
   {
      for (int nRealChar = collapseIndex[startChar]; nRealChar < collapseIndex[startChar + 1]; nRealChar++)
      {
         addOutChar(parsedChars[nRealChar]);
      }
      //addOutChar('*');
   }
   else
   {
      makeSolutionAux(workSize, splitPoint - startChar, startChar, toContext);
      makeSolutionAux(workSize, numChars - (splitPoint - startChar), splitPoint, toContext);
   }

   if (fromSize != toSize)
   {
      addOutChar('<');
      addOutChar('/');
      addOutChar(toSize + '0');
      addOutChar('>');
   }

   if (fromColor != toColor)
   {
      addOutChar('<');
      addOutChar('/');
      addOutChar(colorLetters[toColor]);
      addOutChar('>');
   }

   for (ii = 0; ii < numEm; ii++)
   {
      addOutChar('<');
      addOutChar('/');
      addOutChar('E');
      addOutChar('M');
      addOutChar('>');
   }

   for (ii = 0; ii < numS; ii++)
   {
      addOutChar('<');
      addOutChar('/');
      addOutChar('S');
      addOutChar('>');
   }

   for (ii = 0; ii < numU; ii++)
   {
      addOutChar('<');
      addOutChar('/');
      addOutChar('U');
      addOutChar('>');
   }

   for (ii = 0; ii < numTT; ii++)
   {
      addOutChar('<');
      addOutChar('/');
      addOutChar('T');
      addOutChar('T');
      addOutChar('>');
   }

   for (ii = 0; ii < numI; ii++)
   {
      addOutChar('<');
      addOutChar('/');
      addOutChar('I');
      addOutChar('>');
   }

   for (ii = 0; ii < numB; ii++)
   {
      addOutChar('<');
      addOutChar('/');
      addOutChar('B');
      addOutChar('>');
   }

   for (ii = 0; ii < numPl; ii++)
   {
      addOutChar('<');
      addOutChar('/');
      addOutChar('P');
      addOutChar('L');
      addOutChar('>');
   }

}

void makeSolution(int workSize, int numChars, int startChar)
{
   Context context;
   context.setRoot();
   makeSolutionAux(workSize, numChars, startChar, context);
}

void doWork(int workSize)
{
   for (int numChars = 1; numChars <= workSize; numChars++)
   {
      if (VERBOSE)
      {
         fprintf(stderr, "Preparing partial answer...  ");
      }

      if (outOfTime())
      {
         return;
      }

      {
         int startChar;
         for (startChar = 0; startChar <= (workSize - numChars); startChar++)
         {
            Status &status = getStatus(workSize, numChars, startChar);

            bool totalHasRootColor = hasRootColor(startChar, startChar + numChars - 1);
            bool totalHasRootSize = hasRootSize(startChar, startChar + numChars - 1);

            int bestRootLen = findBest(workSize, numChars, startChar,
               totalHasRootColor,
               totalHasRootSize,
               rootSize,
               rootColor,
               0, 0, 0, 0, 0,
               0, 0);
            status.m_bestRootLen = bestRootLen;
         }

         if (outOfTime())
         {
            return;
         }

         partialLengths[workSize] = 0;
         for (startChar = workSize - 1; startChar >= 0; startChar--)
         {
            for (int curNumChars = 1; (curNumChars <= numChars) && (startChar + curNumChars <= workSize); curNumChars++)
            {
               Status &status = getStatus(workSize, curNumChars, startChar);
               int curLength = partialLengths[startChar + curNumChars] + status.m_bestRootLen;
               if (curNumChars == 1 || curLength < partialLengths[startChar])
               {
                  partialLengths[startChar] = curLength;
                  partialSkips[startChar] = curNumChars;
               }
            }

            if (outOfTime())
            {
               return;
            }
         }

         if (VERBOSE)
         {
            fprintf(stderr, "%d  %d", partialLengths[0], partialLengths[0] + parsedSize);
         }

         int sizeWithChars = partialLengths[0] + parsedSize;
         if (sizeWithChars < bestSize &&
             sizeWithChars < inFileSize)
         {
            outFileSizes[curOutFile] = 0;

            int startChar = 0;
            while (startChar < workSize)
            {
               makeSolution(workSize, partialSkips[startChar], startChar);

               startChar += partialSkips[startChar];

               if (outOfTime())
               {
                  return;
               }
            }

            if (VERBOSE)
            {
               fprintf(stderr, "  %d", outFileSizes[curOutFile]);
            }

            bestSize = sizeWithChars;
            bestOutFile = curOutFile;
            curOutFile = 1 - curOutFile;
         }

         if (VERBOSE)
         {
            fprintf(stderr, "\n");
         }

      }

      if (numChars == workSize)
      {
         // All done!
         return;
      }

      if (VERBOSE)
      {
         fprintf(stderr, "Working on %d...  ", numChars);
      }

      for (int startChar = 0; startChar <= (workSize - numChars); startChar++)
      {
         Status &status = getStatus(workSize, numChars, startChar);

         bool totalHasRootColor = hasRootColor(startChar, startChar + numChars - 1);
         bool totalHasRootSize = hasRootSize(startChar, startChar + numChars - 1);

         unsigned int lowFromColor =
            (totalHasRootColor) ? rootColor : 0;
         unsigned int lowFromSize =
            (totalHasRootSize) ? rootSize : 0;


         int itemAllocSize = 96;
         if (!totalHasRootColor)
         {
            itemAllocSize *= 9;
         }
         if (!totalHasRootSize)
         {
            itemAllocSize *= 11;
         }
         status.m_items = new StatusItem[itemAllocSize];


         bool firstFrom = true;
         int minLen;

         for (unsigned int fromB = 0; fromB <= 1; fromB++)
         {
            for (unsigned int fromI = 0; fromI <= 1; fromI++)
            {
               for (unsigned int fromTT = 0; fromTT <= 1; fromTT++)
               {
                  for (unsigned int fromU = 0; fromU <= 3; fromU++)
                  {
                     for (unsigned int fromSem = 0; fromSem <= 2; fromSem++)
                     {
                        for (unsigned int fromColor = lowFromColor; fromColor <= 8; fromColor++)
                        {
                           for (unsigned int fromSize = lowFromSize; fromSize <= 10; fromSize++)
                           {
                              /*
                              unsigned int fromItemIdx = fromB + (fromI << 1) + (fromTT << 2) + (fromU << 3) +
                                 (((fromColor * 11 + fromSize) * 3 + fromSem) << 5);
                              */

                              unsigned int fromItemIdx = makeItemIdx(
                                 totalHasRootSize,
                                 totalHasRootColor,
                                 fromB,
                                 fromI,
                                 fromTT,
                                 fromU,
                                 fromSem,
                                 fromSize,
                                 fromColor);

                              // inner loop
                              int curLen = findBest(workSize, numChars, startChar,
                                 totalHasRootColor,
                                 totalHasRootSize,
                                 fromSize,
                                 fromColor,
                                 fromB,
                                 fromI,
                                 fromTT,
                                 fromU,
                                 fromSem,
                                 0,
                                 0);

                              if (outOfTime())
                              {
                                 return;
                              }

                              StatusItem &fromItem = status.m_items[fromItemIdx];
                              if (firstFrom)
                              {
                                 firstFrom = false;

                                 status.m_lenBase = curLen;
                                 fromItem.m_lenOffset = 0;

                                 minLen = curLen;
                              }
                              else
                              {
                                 fromItem.m_lenOffset = curLen - status.m_lenBase;

                                 if (curLen < minLen)
                                 {
                                    minLen = curLen;
                                 }
                              }

                           }
                        }
                     }
                  }
               }
            }
         }

         int lenAdjust = status.m_lenBase - minLen;
         status.m_lenBase = minLen;
         for (int nItem = 0; nItem < itemAllocSize; nItem++)
         {
            status.m_items[nItem].m_lenOffset += lenAdjust;
         }

      }
   }
}

int main(int argc, char* argv[])
{
   time_t startTime = time(0);

   int timeLimit = 180;
   if (argc > 1)
   {
      int temp = atoi(argv[1]);
      if (temp > 0)
      {
         timeLimit = temp;
      }
   }
   endTime = startTime + timeLimit;
   gapStart = startTime;

   if (VERBOSE)
   {
      fprintf(stderr, "Time limit: %d\n", timeLimit);
   }

   invertColorLetters();

   if (VERBOSE)
   {
      fprintf(stderr, "sizeof(Context) == %d\n", sizeof(Context));
      fprintf(stderr, "sizeof(StatusItem) == %d\n", sizeof(StatusItem));
      fprintf(stderr, "sizeof(Status) == %d\n", sizeof(Status));
   }

   readFile();

   if (VERBOSE)
   {
      //writeInFile();
      //fprintf(stderr, "Hello World!\n");
      fprintf(stderr, "inFileSize = %d\n", inFileSize);
   }

   parseFile();

   if (VERBOSE)
   {
      fprintf(stderr, "parsedSize = %d\n", parsedSize);

      //writeParsedChars();
   }

   //makeSimpleSolution();

   int workSize = prepareWork();

   if (VERBOSE)
   {
      fprintf(stderr, "workSize = %d\n", workSize);
   }

   doWork(workSize);

   if (VERBOSE)
   {
      //fprintf(stderr, "\nMaking solution...\n");
   }

   // makeSolution(workSize);

   if (bestSize < inFileSize)
   {
      if (VERBOSE)
      {
         fprintf(stderr, "Final sizes:  %d  %d\n", outFileSizes[bestOutFile] - parsedSize, outFileSizes[bestOutFile]);
      }

      writeOutFile(bestOutFile);
   }
   else
   {
      writeInFile();
   }

   if (VERBOSE)
   {
      fprintf(stderr, "\nLongest gap: %d\n", longestGap);
   }

   return 0;
}