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

/* Global buffer of characters */
typedef struct
{
   int x, y;  /* Character position */
   int code;  /* Character code point */
} Char;
static Char *characters = NULL;
static int character_count = 0;
static int character_capacity = 1;
static int min_y = 0;
static int max_y = 0;

/* MergeSort all characters by position */
static void MergeSort(int x, int y)
{
   int m = (x + y) / 2;
   int i, j, r, w;

   if( m == x )
      return;
   MergeSort(x, m);
   MergeSort(m, y);
   for(i = x, j = m, w = character_count + x; w < character_count + y; w++)
   {
      if( i < m )
      {
         if( j < y )
         {
            if( characters[i].y < characters[j].y ||
                (characters[i].y == characters[j].y &&
                 characters[i].x < characters[j].x) )
            {
               r = i++;
            }
            else
            {
               r = j++;
            }
         }
         else
         {
            r = i++;
         }
      }
      else
      {
         r = j++;
      }
      characters[w].x = characters[r].x;
      characters[w].y = characters[r].y;
      characters[w].code = characters[r].code;
   }
   for(w = x, r = character_count + x; w < y; r++, w++)
   {
      characters[w].x = characters[r].x;
      characters[w].y = characters[r].y;
      characters[w].code = characters[r].code;
   }
}

/* Fisher-yates shuffle */
static void Shuffle()
{
   int i, j, tmp;

   for(j = character_count; --j > 0;)
   {
      i = rand() % (j + 1);
      tmp = characters[i].x;
      characters[i].x = characters[j].x;
      characters[j].x = tmp;
      tmp = characters[i].y;
      characters[i].y = characters[j].y;
      characters[j].y = tmp;
      tmp = characters[i].code;
      characters[i].code = characters[j].code;
      characters[j].code = tmp;
   }
}

/* Add a single character to global buffer */
static void AddChar(int x, int y, int code)
{
   /* Since we always double the amount of memory allocated when the
      next character reaches capacity, we always have at least twice
      as much memory as number of characters loaded.  This means we
      already have the spare space needed for MergeSort.             */
   if( character_count + 1 >= character_capacity )
   {
      character_capacity *= 2;
      characters = (Char*)realloc(characters,
                                  character_capacity * sizeof(Char));
      if( characters == NULL )
      {
         fputs("Out of memory\n", stderr);
         exit(EXIT_FAILURE);
      }
   }
   characters[character_count].x = x;
   characters[character_count].y = y;
   characters[character_count].code = code;
   character_count++;
   if( min_y > y ) min_y = y;
   if( max_y < y ) max_y = y;
}

/* Read UTF-8 bytes */
static int ReadUTF8(FILE *infile, int count)
{
   int c = 0;
   for(; count > 0; count--)
      c = (c << 6) | (fgetc(infile) & 0x3f);
   return c;
}

/* Write UTF-8 bytes */
static void WriteUTF8(int code, FILE *outfile)
{
   if( code < 0x80 )
   {
      fputc(code, outfile);
   }
   else if( code < (1 << (5 + 6)) )
   {
      fputc(0xc0 | ((code >> 6) & 0x1f), outfile);
      fputc(0x80 | (code & 0x3f), outfile);
   }
   else if( code < (1 << (4 + 6 + 6)) )
   {
      fputc(0xe0 | ((code >> 12) & 0x0f), outfile);
      fputc(0x80 | ((code >> 6) & 0x3f), outfile);
      fputc(0x80 | (code & 0x3f), outfile);
   }
   else
   {
      fputc(0xf0 | ((code >> 18) & 0x07), outfile);
      fputc(0x80 | ((code >> 12) & 0x3f), outfile);
      fputc(0x80 | ((code >> 6) & 0x3f), outfile);
      fputc(0x80 | (code & 0x3f), outfile);
   }
}

/* Get width of character, returns 1 for half width and 2 for full width */
static int GetCharWidth(int c)
{
   static const int ranges[11][2] =
   {
      {0x1100, 0x115f},
      {0x2329, 0x232a},
      {0x2e80, 0x303e},
      {0x3040, 0xa4cf},
      {0xac00, 0xd7a3},
      {0xf900, 0xfaff},
      {0xfe10, 0xfe19},
      {0xfe30, 0xfe6f},
      {0xff00, 0xff60},
      {0xffe0, 0xffe6},
      {0x20000, 0x3fffd}
   };
   int i;

   for(i = 0; i < 11; i++)
   {
      if( c >= ranges[i][0] && c <= ranges[i][1] )
         return 2;
   }
   return 1;
}

/* Update cursor based on escape sequence */
static void UpdateCursor(FILE *infile, int *x, int *y)
{
   int param = 0;
   int c;

   while( (c = fgetc(infile)) != EOF )
   {
      if( c >= '0' && c <= '9' )
      {
         param = param * 10 + c - '0';
      }
      else if( c == ';' )
      {
         /* Delimiter used for multi-param sequences (such as colors),
            but we don't care about those.                             */
      }
      else if( c == 'A' )
      {
         /* Cursor up */
         *y -= param;
         return;
      }
      else if( c == 'B' )
      {
         /* Cursor down */
         *y += param;
         return;
      }
      else if( c == 'C' )
      {
         /* Cursor forward */
         *x += param;
         return;
      }
      else if( c == 'D' )
      {
         /* Cursor backward */
         *x -= param;
         if( *x < 0 )
            *x = 0;
         return;
      }
      else
      {
         /* Some escape sequence that we don't care about, silently ignored */
         return;
      }
   }
}

/* Load input characters to global buffer */
static void LoadInput(FILE *infile)
{
   int c, x = 0, y = 0;
   int state = 0;  /* 0 = normal, 1 = seen ESC */

   while( (c = fgetc(infile)) != EOF )
   {
      if( state != 0 )
      {
         if( c == '[' )
         {
            /* Escape sequence */
            UpdateCursor(infile, &x, &y);
            continue;
         }
         state = 0;
      }
      if( c == 0x1b )
      {
         /* Start of escape sequence */
         state = 1;
         continue;
      }
      else if( (c & 0xe0) == 0xc0 )
      {
         /* 2-byte UTF-8 sequence */
         c = ((c & 0x1f) << 6) | ReadUTF8(infile, 1);
         AddChar(x, y, c);
         x += GetCharWidth(c);
      }
      else if( (c & 0xf0) == 0xe0 )
      {
         /* 3-byte UTF-8 sequence */
         c = ((c & 0x0f) << 12) | ReadUTF8(infile, 2);
         AddChar(x, y, c);
         x += GetCharWidth(c);
      }
      else if( (c & 0xf8) == 0xf0 )
      {
         /* 4-byte UTF-8 sequence */
         c = ((c & 0x07) << 18) | ReadUTF8(infile, 3);
         AddChar(x, y, c);
         x += GetCharWidth(c);
      }
      else if( c == '\n' )
      {
         /* Newline: update cursor but don't buffer character */
         y++;
         x = 0;
      }
      else if( c == ' ' )
      {
         /* Space: update cursor but don't buffer character */
         x++;
      }
      else if( c == '\t' )
      {
         /* Tab: update cursor but don't buffer character */
         for(x++; x % 8; x++);
      }
      else if( c < 32 )
      {
         /* Other control characters (ignored) */
      }
      else
      {
         /* Single byte character */
         AddChar(x++, y, c);
      }
   }
}

/* Output characters in sorted order */
static void OutputSorted(FILE *outfile)
{
   int i, x, y;

   /* Write one sentinel character to mark the end.  This for seeking
      one character ahead when checking duplicates.  We don't have to
      worry about out of bounds writes since the buffer is always at
      least twice as large as number of characters.                   */
   characters[character_count].x = -1;
   for(i = x = y = 0; i < character_count; i++)
   {
      while( y < characters[i].y )
      {
         fputc('\n', outfile);
         y++;
         x = 0;
      }
      while( x < characters[i].x )
      {
         fputc(' ', outfile);
         x++;
      }

      /* Seek ahead in case if there are overlaps.  We want to take
         the last character that is drawn at this position to simulate
         overlaps.                                                     */
      while( characters[i + 1].y == characters[i].y &&
             characters[i + 1].x == characters[i].x )
      {
         i++;
      }
      WriteUTF8(characters[i].code, outfile);
      x += GetCharWidth(characters[i].code);
   }

   /* Always end with newline */
   if( x > 0 )
      fputc('\n', outfile);
}

/* Output characters in shuffled order */
static void OutputShuffled(FILE *outfile)
{
   int i, x, y;

   srand(time(NULL));
   Shuffle();

   /* Preallocate vertical space */
   for(i = 0; i < max_y - min_y + 1; i++)
      fputc('\n', outfile);

   for(i = x = 0, y = max_y + 1; i < character_count; i++)
   {
      if( y < characters[i].y )
      {
         fprintf(outfile, "\x1b[%dB", characters[i].y - y);
      }
      else if( y > characters[i].y )
      {
         fprintf(outfile, "\x1b[%dA", y - characters[i].y);
      }
      if( x < characters[i].x )
      {
         fprintf(outfile, "\x1b[%dC", characters[i].x - x);
      }
      else if( x > characters[i].x )
      {
         fprintf(outfile, "\x1b[%dD", x - characters[i].x);
      }
      WriteUTF8(characters[i].code, outfile);
      x = characters[i].x + GetCharWidth(characters[i].code);
      y = characters[i].y;
   }

   /* Move cursor to last line */
   if( y < max_y )
      fprintf(outfile, "\x1b[%dB", max_y - y);
   fputc('\n', outfile);
}

int main(int argc, char **argv)
{
   LoadInput(stdin);
   if( characters == NULL )
      return 0;
   MergeSort(0, character_count);
   if( argc == 1 )
   {
      OutputSorted(stdout);
   }
   else
   {
      OutputShuffled(stdout);
   }
   return 0;
}