/* Simple FORTRAN-style Markov-chain text generator.
   Cf. vecmarkov.py, the 20× slower version.
*/

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

/* Feeding this program more than 4 GiB of input would be foolish, but
   we might as well make it work correctly.
*/
long long model[256][256];

int main() {
  srandom(time(NULL));

  int c, last = getchar();
  if (last == EOF) return -1;

  while ((c = getchar()) != EOF) {
    model[last][c]++;
    last = c;
  }

  /* Prefix sum to compute empirical CDF in place. */
  for (size_t ii = 0; ii != 256; ii++) {
    for (size_t jj = 1; jj != 256; jj++) {
      model[ii][jj] += model[ii][jj-1];
    }
  }

  for (size_t ii = 0; ii != 1024; ii++) {
    putchar(c);

    while (!model[c][255]) c = random() & 0xff; /* escape dead ends */
    long long x = ((long long)random() << 32 | random()) % model[c][255];

    /* To generate a random variate according to the CDF, we use
       binary search, in the variant Python bisect.bisect_right: if x
       already appears in the list, the result points just beyond the
       rightmost x already there.
    */
    int lo = 0, hi = 255, mid;
    while (lo != hi) {
      mid = lo + (hi - lo)/2;   /* unnecessary - for 255, but whatever */
      if (model[c][mid] > x) {
        hi = mid;               /* mid is a possible result */
      } else {
        lo = mid + 1;           /* mid is not a possible result */
      }
    }

    c = lo;
  }

  return 0;
}