#include <algorithm>
#include <cassert>
#include <cstdlib>
#include <cstdio>
#include <ctime>
#include <iostream>
#include <map>
#include <string>
#include <vector>
using namespace std;

// Notes on compiling
// ------------------
// 
// I use the command 'g++ flip.cc -O3 -lrt' to compile.
// If your environment doesn't have clock_gettime, you can set USE_TIME to 0
// and remove the -lrt with no ill effects.
// If your environment doesn't have /dev/urandom, you'll get a warning and
// the random number generator will be lower-quality, but otherwise it'll be
// fine.

#define USE_TIME 0

string PI_DIGS_16 =
"243F6A8885A308D313198A2E03707344A4093822299F31D0082EFA98EC4E6C89"
"452821E638D01377BE5466CF34E90C6CC0AC29B7C97C50DD3F84D5B5B5470917"
"9216D5D98979FB1BD1310BA698DFB5AC2FFD72DBD01ADFB7B8E1AFED6A267E96"
"BA7C9045F12C7F9924A19947B3916CF70801F2E2858EFC16636920D871574E69"
"A458FEA3F4933D7E0D95748F728EB658718BCD5882154AEE7B54A41DC25A59B5"
"9C30D5392AF26013C5D1B023286085F0CA417918B8DB38EF8E79DCB0603A180E"
"6C9E0E8BB01E8A3ED71577C1BD314B2778AF2FDA55605C60E65525F3AA55AB94"
"5748986263E8144055CA396A2AAB10B6B4CC5C341141E8CEA15486AF7C72E993"
"B3EE1411636FBC2A2BA9C55D741831F6CE5C3E169B87931EAFD6BA336C24CF5C"
"7A325381289586773B8F48986B4BB9AFC4BFE81B6628219361D809CCFB21A991"
"487CAC605DEC8032EF845D5DE98575B1DC262302EB651B8823893E81D396ACC5"
"0F6D6FF383F442392E0B4482A484200469C8F04A9E1F9B5E21C66842F6E96C9A"
"670C9C61ABD388F06A51A0D2D8542F68960FA728AB5133A36EEF0B6C137A3BE4"
"BA3BF0507EFB2A98A1F1651D39AF017666CA593E82430E888CEE8619456F9FB4"
"7D84A5C33B8B5EBEE06F75D885C12073401A449F56C16AA64ED3AA62363F7706"
"1BFEDF72429B023D37D0D724D00A1248DB0FEAD349F1C09B075372C980991B7B"
"25D479D8F6E8DEF7E3FE501AB6794C3B976CE0BD04C006BAC1A94FB6409F60C4"
"5E5C9EC2196A246368FB6FAF3E6C53B51339B2EB3B52EC6F6DFC511F9B30952C"
"CC814544AF5EBD09BEE3D004DE334AFD660F2807192E4BB3C0CBA85745C8740F"
"D20B5F39B9D3FBDB5579C0BD1A60320AD6A100C6402C7279679F25FEFB1FA3CC"
"8EA5E9F8DB3222F83C7516DFFD616B152F501EC8AD0552AB323DB5FAFD238760"
"53317B483E00DF829E5C57BBCA6F8CA01A87562EDF1769DBD542A8F6287EFFC3"
"AC6732C68C4F5573695B27B0BBCA58C8E1FFA35DB8F011A010FA3D98FD2183B8"
"4AFCB56C2DD1D35B9A53E479B6F84565D28E49BC4BFB9790E1DDF2DAA4CB7E33"
"62FB1341CEE4C6E8EF20CADA36774C01D07E9EFE2BF11FB495DBDA4DAE909198"
"EAAD8E716B93D5A0D08ED1D0AFC725E08E3C5B2F8E7594B78FF6E2FBF2122B64"
"8888B812900DF01C4FAD5EA0688FC31CD1CFF191B3A8C1AD2F2F2218BE0E1777"
"EA752DFE8B021FA1E5A0CC0FB56F74E818ACF3D6CE89E299B4A84FE0FD13E0B7"
"7CC43B81D2ADA8D9165FA2668095770593CC7314211A1477E6AD206577B5FA86"
"C75442F5FB9D35CFEBCDAF0C7B3E89A0D6411BD3AE1E7E4900250E2D2071B35E"
"226800BB57B8E0AF2464369BF009B91E5563911D59DFA6AA78C14389D95A537F"
"207D5BA202E5B9C5832603766295CFA911C819684E734A41B3472DCA7B14A94A"
"1B5100529A532915D60F573FBC9BC6E42B60A47681E6740008BA6FB5571BE91F"
"F296EC6B2A0DD915B6636521E7B9F9B6FF34052EC585566453B02D5DA99F8FA1"
"08BA47996E85076A4B7A70E9B5B32944DB75092EC4192623AD6EA6B049A7DF7D"
"9CEE60B88FEDB266ECAA8C71699A17FF5664526CC2B19EE1193602A575094C29"
"A0591340E4183A3E3F54989A5B429D656B8FE4D699F73FD6A1D29C07EFE830F5"
"4D2D38E6F0255DC14CDD20868470EB266382E9C6021ECC5E09686B3F3EBAEFC9"
"3C9718146B6A70A1687F358452A0E286B79C5305AA5007373E07841C7FDEAE5C"
"8E7D44EC5716F2B8B03ADA37F0500C0DF01C1F040200B3FFAE0CF51A3CB574B2"
"25837A58DC0921BDD19113F97CA92FF69432477322F547013AE5E58137C2DADC"
"C8B576349AF3DDA7A94461460FD0030EECC8C73EA4751E41E238CD993BEA0E2F"
"3280BBA1183EB3314E548B384F6DB9086F420D03F60A04BF2CB8129024977C79"
"5679B072BCAF89AFDE9A771FD9930810B38BAE12DCCF3F2E5512721F2E6B7124"
"501ADDE69F84CD877A5847187408DA17BC9F9ABCE94B7D8CEC7AEC3ADB851DFA"
"63094366C464C3D2EF1C18473215D908DD433B3724C2BA1612A14D432A65C451"
"50940002133AE4DD71DFF89E10314E5581AC77D65F11199B043556F1D7A3C76B"
"3C11183B5924A509F28FE6ED97F1FBFA9EBABF2C1E153C6E86E34570EAE96FB1"
"860E5E0A5A3E2AB3771FE71C4E3D06FA2965DCB999E71D0F803E89D65266C825"
"2E4CC9789C10B36AC6150EBA94E2EA78A5FC3C531E0A2DF4F2F74EA7361D2B3D"
"1939260F19C279605223A708F71312B6EBADFE6EEAC31F66E3BC4595A67BC883"
"B17F37D1018CFF28C332DDEFBE6C5AA56558218568AB9802EECEA50FDB2F953B"
"2AEF7DAD5B6E2F841521B62829076170ECDD4775619F151013CCA830EB61BD96"
"0334FE1EAA0363CFB5735C904C70A239D59E9E0BCBAADE14EECC86BC60622CA7"
"9CAB5CABB2F3846E648B1EAF19BDF0CAA02369B9655ABB5040685A323C2AB4B3"
"319EE9D5C021B8F79B540B19875FA09995F7997E623D7DA8F837889A97E32D77"
"11ED935F166812810E358829C7E61FD696DEDFA17858BA9957F584A51B227263"
"9B83C3FF1AC24696CDB30AEB532E30548FD948E46DBC312858EBF2EF34C6FFEA"
"FE28ED61EE7C3C735D4A14D9E864B7E342105D14203E13E045EEE2B6A3AAABEA"
"DB6C4F15FACB4FD0C742F442EF6ABBB5654F3B1D41CD2105D81E799E86854DC7"
"E44B476A3D816250CF62A1F25B8D2646FC8883A0C1C7B6A37F1524C369CB7492"
"47848A0B5692B285095BBF00AD19489D1462B17423820E0058428D2A0C55F5EA"
"1DADF43E233F70613372F0928D937E41D65FECF16C223BDB7CDE3759CBEE7460"
"4085F2A7CE77326EA607808419F8509EE8EFD85561D99735A969A7AAC50C06C2"
"5A04ABFC800BCADC9E447A2EC3453484FDD567050E1E9EC9DB73DBD3105588CD"
"675FDA79E3674340C5C43465713E38D83D28F89EF16DFF20153E21E78FB03D4A"
"E6E39F2BDB83ADF7E93D5A68948140F7F64C261C94692934411520F77602D4F7"
"BCF46B2ED4A20068D40824713320F46A43B7D4B7500061AF1E39F62E97244546"
"14214F74BF8B88404D95FC1D96B591AF70F4DDD366A02F45BFBC09EC03BD9785"
"7FAC6DD031CB850496EB27B355FD3941DA2547E6ABCA0A9A28507825530429F4"
"0A2C86DAE9B66DFB68DC1462D7486900680EC0A427A18DEE4F3FFEA2E887AD8C"
"B58CE0067AF4D6B6AACE1E7CD3375FECCE78A399406B2A4220FE9E35D9F385B9"
"EE39D7AB3B124E8B1DC9FAF74B6D185626A36631EAE397B23A6EFA74DD5B4332"
"6841E7F7CA7820FBFB0AF54ED8FEB397454056ACBA48952755533A3A20838D87"
"FE6BA9B7D096954B55A867BCA1159A58CCA9296399E1DB33A62A4A563F3125F9"
"5EF47E1C9029317CFDF8E80204272F7080BB155C05282CE395C11548E4C66D22"
"48C1133FC70F86DC07F9C9EE41041F0F404779A45D886E17325F51EBD59BC0D1"
"F2BCC18F41113564257B7834602A9C60DFF8E8A31F636C1B0E12B4C202E1329E"
"AF664FD1CAD181156B2395E0333E92E13B240B62EEBEB92285B2A20EE6BA0D99"
"DE720C8C2DA2F728D012784595B794FD647D0862E7CCF5F05449A36F877D48FA"
"C39DFD27F33E8D1E0A476341992EFF743A6F6EABF4F8FD37A812DC60A1EBDDF8"
"991BE14CDB6E6B0DC67B55106D672C372765D43BDCD0E804F1290DC7CC00FFA3"
"B5390F92690FED0B667B9FFBCEDB7D9CA091CF0BD9155EA3BB132F88515BAD24"
"7B9479BF763BD6EB37392EB3CC1159798026E297F42E312D6842ADA7C66A2B3B"
"12754CCC782EF11C6A124237B79251E706A1BBE64BFB63501A6B101811CAEDFA"
"3D25BDD8E2E1C3C9444216590A121386D90CEC6ED5ABEA2A64AF674EDA86A85F"
"BEBFE98864E4C3FE9DBC8057F0F7C08660787BF86003604DD1FD8346F6381FB0"
"7745AE04D736FCCC83426B33F01EAB71B08041873C005E5F77A057BEBDE8AE24"
"55464299BF582E614E58F48FF2DDFDA2F474EF388789BDC25366F9C3C8B38E74"
"B475F25546FCD9B97AEB26618B1DDF84846A0E79915F95E2466E598E20B45770"
"8CD55591C902DE4CB90BACE1BB8205D011A862487574A99EB77F19B6E0A9DC09"
"662D09A1C4324633E85A1F0209F0BE8C4A99A0251D6EFE101AB93D1D0BA5A4DF"
"A186F20F2868F169DCB7DA83573906FEA1E2CE9B4FCD7F5250115E01A70683FA"
"A002B5C40DE6D0279AF88C27773F8641C3604C0661A806B5F0177A28C0F586E0"
"006058AA30DC7D6211E69ED72338EA6353C2DD94C2C21634BBCBEE5690BCB6DE"
"EBFC7DA1CE591D766F05E4094B7C018839720A3D7C927C2486E3725F724D9DB9"
"1AC15BB4D39EB8FCED54557808FCA5B5D83D7CD34DAD0FC41E50EF5EB161E6F8"
"A28514D96C51133C6FD5C7E756E14EC4362ABFCEDDC6C837D79A323492638212"
"670EFA8E406000E03A39CE37D3FAF5CFABC277375AC52D1B5CB0679E4FA33742"
"D382274099BC9BBED5118E9DBF0F7315D62D1C7EC700C47BB78C1B6B21A19045"
"B26EB1BE6A366EB45748AB2FBC946E79C6A376D26549C2C8530FF8EE468DDE7D"
"D5730A1D4CD04DC62939BBDBA9BA4650AC9526E8BE5EE304A1FAD5F06A2D519A"
"63EF8CE29A86EE22C089C2B843242EF6A51E03AA9CF2D0A483C061BA9BE96A4D"
"8FE51550BA645BD62826A2F9A73A3AE14BA99586EF5562E9C72FEFD3F752F7DA"
"3F046F6977FA0A5980E4A91587B086019B09E6AD3B3EE593E990FD5A9E34D797"
"2CF0B7D9022B8B5196D5AC3A017DA67DD1CF3ED67C7D2D281F9F25CFADF2B89B"
"5AD6B4725A88F54CE029AC71E019A5E647B0ACFDED93FA9BE8D3C48D283B57CC"
"F8D5662979132E28785F0191ED756055F7960E44E3D35E8C15056DD488F46DBA"
"03A161250564F0BDC3EB9E153C9057A297271AECA93A072A1B3F6D9B1E6321F5"
"F59C66FB26DCF3197533D928B155FDF5035634828ABA3CBB28517711C20AD9F8"
"ABCC5167CCAD925F4DE817513830DC8E379D58629320F991EA7A90C2FB3E7BCE"
"5121CE64774FBE32A8B6E37EC3293D4648DE53696413E680A2AE0810DD6DB224"
"69852DFD09072166B39A460A6445C0DD586CDECF1C20C8AE5BBEF7DD1B588D40"
"CCD2017F6BB4E3BBDDA26A7E3A59FF453E350A44BCB4CDD572EACEA8FA6484BB"
"8D6612AEBF3C6F47D29BE463542F5D9EAEC2771BF64E6370740E0D8DE75B1357"
"F8721671AF537D5D4040CB084EB4E2CC34D2466A0115AF84E1B0042895983A1D"
"06B89FB4CE6EA0486F3F3B823520AB82011A1D4B277227F8611560B1E7933FDC"
"BB3A792B344525BDA08839E151CE794B2F32C9B7A01FBAC9E01CC87EBCC7D1F6"
"CF0111C3A1E8AAC71A908749D44FBD9AD0DADECBD50ADA380339C32AC6913667"
"8DF9317CE0B12B4FF79E59B743F5BB3AF2D519FF27D9459CBF97222C15E6FC2A"
"0F91FC719B941525FAE59361CEB69CEBC2A8645912BAA8D1B6C1075EE3056A0C"
"10D25065CB03A442E0EC6E0E1698DB3B4C98A0BE3278E9649F1F9532E0D392DF"
"D3A0342B8971F21E1B0A74414BA3348CC5BE7120C37632D8DF359F8D9B992F2E"
"E60B6F470FE3F11DE54CDA541EDAD891CE6279CFCD3E7E6F1618B166FD2C1D05"
"848FD2C5F6FB2299F523F357A632762393A8353156CCCD02ACF081625A75EBB5"
"6E16369788D273CCDE96629281B949D04C50901B71C65614E6C6C7BD327A140A"
"45E1D006C3F27B9AC9AA53FD62A80F00BB25BFE235BDD2F671126905B2040222"
"B6CBCF7CCD769C2B53113EC01640E3D338ABBD602547ADF0BA38209CF746CE76"
"77AFA1C52075606085CBFE4E8AE88DD87AAAF9B04CF9AA7E1948C25C02FB8A8C"
"01C36AE4D6EBE1F990D4F869A65CDEA03F09252DC208E69FB74E6132CE77E25B"
"578FDFE33AC372E6";
string PI_DIGS_2;
string MORSE_CODE[26] = {
  ".-", "-...", "-.-.", "-..", ".",
  "..-.", "--.", "....", "..", ".---",
  "-.-", ".-..", "--", "-.", "---",
  ".--.", "--.-", ".-.", "...", "-",
  "..-", "...-", ".--", "-..-", "-.--", "--.."};

string MESSAGE1 = "HARDYNUMBLOCKS";
string MESSAGE2 = "PLEASEHELPTRAPPEDINCOINFLIPPINGFACTORYJUSTKIDDINGTHUUUTUXUUUHUHTUUHUH";
int MESSAGE2_BLOCK_SIZE = 1729;
int PI_PIECE_SIZE = 14;
int PI_PIECE_DOT_GAP = 1;
int PI_PIECE_DASH_GAP = 3;
int PI_PIECE_SPACE_GAP = 0;
string FINAL_CODE = "THUUUTUXUUUHUHTUUHUH";
int FINAL_CODE_XPOS;
string FINAL_IMAGE =
".XXXXX.........XX.XX..."
".XXXXX....XX..XXXXXXXX."
".XXXX....X..X...XX.XX.."
".XXX....X....X........."
".......X......X........"
"......XXX.XX...X......."
".....XXXXXXXXXXXX......"
"....XXXXXXXXXXXXXX....."
"...XXXXXXXXXXXXXXXX...."
".XXXXXXXXXXXXXXXXXXXXX."
"......................."
"....X.X.X.X.X.X.X.X...."
".......................";
FILE *urandom;


void Init() {
  for (int i = 0; i < PI_DIGS_16.size(); i++) {
    int dig = isdigit(PI_DIGS_16[i]) ? PI_DIGS_16[i] : PI_DIGS_16[i]-'A'+10;
    PI_DIGS_2 += (dig&8)?'1':'0';
    PI_DIGS_2 += (dig&4)?'1':'0';
    PI_DIGS_2 += (dig&2)?'1':'0';
    PI_DIGS_2 += (dig&1)?'1':'0';
  }
  string codechars = "HTUX";
  for (int i = 0; i < FINAL_CODE.size(); i++)
    assert(codechars.find(FINAL_CODE[i]) != -1);
  FINAL_CODE_XPOS = FINAL_CODE.find('X');
  assert(FINAL_CODE_XPOS != -1);
  assert(FINAL_CODE.find('X', FINAL_CODE_XPOS+1) == -1);
  urandom = fopen("/dev/urandom", "r");
  if (!urandom) cerr << "WARNING: No access to /dev/urandom!";
}

inline unsigned short Rand() {
  static unsigned short lastret = 11111, lastret2 = 22222;
  unsigned short ret = 0;
  if (urandom) {
    int read = fread(&ret, sizeof(unsigned short), 1, urandom);
    assert(1 == read);
  } else {
    ret = (rand()>>3)&65535;
  }

  // For good measure, xor with digits of pi and the timer.
  int x = lastret;
  for (int i = 0; i < 16; i++, x += lastret2)
    if (PI_DIGS_2[x % PI_DIGS_2.size()] == '1') ret ^= (1<<i);
#if USE_TIME
  struct timespec ts;
  clock_gettime(CLOCK_REALTIME, &ts);
  ret ^= (short)ts.tv_nsec;
#endif

  lastret2 = lastret;
  lastret = ret;
  return ret;
}

struct Flipper {
  static int prob6[64];
  static void Encode1(string message) {
    assert(message.size() < 15);
    for (int i = 0; i < message.size(); i++)
      assert(message[i] >= 'A' && message[i] <= 'Z');
    for (int i = 0; i < message.size(); i++)
    for (int j = i+1; j < message.size(); j++)
      assert(message[i] != message[j]);

    // Encodes a message into the frequencies of strings of 7 bits.
    // Format: 0lllll0 and 1lllll1 occur 3N% more often than expected.
    //         0lllll1 and 1lllll0 occur 3N% less often than expected.
    // N is the ordering index, lllll is the letter.
    // Doing it this way means that 6-bit string frequencies will remain equal.
    for (int i = 0; i < 64; i++) prob6[i] = 32768;
    for (int i = 0; i < message.size(); i++) {
      int let = message[i]-'A'+1;
      prob6[let] = 32768*(100-6-4*i)/100;
      prob6[let+32] = 65536 - prob6[let];
    }
  }

  static string block_correlation;
  static int pie_block_index;
  static void Encode2(string message, int blocksize) {
    block_correlation = string(blocksize, false);

    // Encodes a message into the correlation between the nth coin flip and
    // the (n-blocksize)th coin flip.  Some positions "resist" flipping from
    // H to T or T to H by about 10%.  The gaps between these positions spell
    // out letters.
    int pos = 30;
    block_correlation[pos] = true;
    for (int i = 0; i < message.size(); i++) {
      pos += (message[i]-'A'+1);
      assert(pos < blocksize-30);
      block_correlation[pos] = true;
    }
    pie_block_index = pos+1;
  }

  static vector<int> pie_morse_indices;
  static void Encode3(string message) {
    string pie_morse_code;
    for (int i = 0; i < message.size(); i++) {
      if (i) pie_morse_code += ' ';
      assert(message[i] >= 'A' && message[i] <= 'Z');
      pie_morse_code += MORSE_CODE[message[i]-'A'];
    }

    pie_morse_indices.clear();
    pie_morse_indices.push_back(0);
    for (int i = 0; i < pie_morse_code.size(); i++) {
      int gap = (pie_morse_code[i] == '.' ? PI_PIECE_DOT_GAP :
                 pie_morse_code[i] == '-' ? PI_PIECE_DASH_GAP :
                 PI_PIECE_SPACE_GAP);
      pie_morse_indices.push_back(pie_morse_indices.back() +
          PI_PIECE_SIZE + gap);
    }
  }

  static void Precompute() {
    Encode1(MESSAGE1);
    Encode2(MESSAGE2, MESSAGE2_BLOCK_SIZE);
    Encode3(FINAL_CODE);
  }

  int last6;
  string lastblock;
  int lastblockpos;
  int piebasepos, piemorsepos;
  int imagepos;
  vector<int> lookahead;
  vector<int> lookahead_fixed;
  Flipper() {
    last6 = Rand()&63;
    for (int i = 0; i < block_correlation.size(); i++) lastblock += Rand()%2;
    lastblockpos = Rand() % block_correlation.size();
    piebasepos = Rand() % 100;  // Start near beginning of pi
    piemorsepos = Rand() % pie_morse_indices.size();
    imagepos = Rand() % FINAL_IMAGE.size();
    lookahead.resize(FINAL_CODE.size());
    lookahead_fixed.resize(FINAL_CODE.size());
    for (int i = 0; i < lookahead.size(); i++) lookahead[i] = Rand()%2;
    for (int i = 0; i < lookahead.size(); i++) Flip();
  }

  bool Flip() {
    bool ret, retfixed = false;
    if (lastblockpos >= pie_block_index &&
        lastblockpos <= pie_block_index + PI_PIECE_SIZE) {
      ret = (PI_DIGS_2[piebasepos + pie_morse_indices[piemorsepos] +
                           lastblockpos-pie_block_index] == '1');
      retfixed = true;
      if (lastblockpos == pie_block_index + PI_PIECE_SIZE) {
        ret = !ret;  // Guarantee a mismatch.
        ++piemorsepos;
        if (piemorsepos == pie_morse_indices.size()) {
          // Start the message over again.
          piemorsepos = 0;
          piebasepos = Rand() % 100;
        }
      }
    } else {
      ret = (Rand() < prob6[last6]);
      if (ret != lastblock[lastblockpos] && block_correlation[lastblockpos]) {
        // 50% of the time we'll resist the change.
        if (Rand() < 32768) ret = lastblock[lastblockpos];
      }
    }
    last6 = ((last6<<1)&63)+ret;
    lastblock[lastblockpos] = ret;
    lastblockpos = (lastblockpos+1) % block_correlation.size();

    // Insert a bit from the final image if necessary
    bool valid = true;
    for (int i = 0; valid && i < lookahead.size(); i++) {
      // Use fixed bits to disprove the pattern first, for safety.
      if (!lookahead_fixed[i]) continue;
      if (FINAL_CODE[i] == 'T' && !lookahead[i]) valid = false;
      if (FINAL_CODE[i] == 'H' && lookahead[i]) valid = false;
    }
    for (int i = 0; valid && i < lookahead.size(); i++) {
      if (FINAL_CODE[i] == 'T' && !lookahead[i]) {
        lookahead_fixed[i] = true;
        valid = false;
      }
      if (FINAL_CODE[i] == 'H' && lookahead[i]) {
        lookahead_fixed[i] = true;
        valid = false;
      }
    }
    if (valid) {
      bool use_bit = true;
      if (lookahead[FINAL_CODE_XPOS] != (FINAL_IMAGE[imagepos]=='X')) {
        // We need to change this bit.  However, it's possible it's already
        // fixed, in which case we can't; pick a different bit.
        if (lookahead_fixed[FINAL_CODE_XPOS]) {
          int i;
          for (i = 0; i < FINAL_CODE.size(); i++)
            if ((FINAL_CODE[i] == 'H' || FINAL_CODE[i] == 'T') &&
                !lookahead_fixed[i])
              break;
          if (i == FINAL_CODE.size()) {
            // This is bad, but also quite rare.  The image is more important
            // than the Morse code, so we'll settle for slightly screwing up
            // the Morse code.
            cerr << "Whoops!  The unthinkable happened!" << endl;
            i = FINAL_CODE.size()-1;
          }
          lookahead[i] = !lookahead[i];
          lookahead_fixed[i] = true;
          use_bit = false;
        } else {
          lookahead[FINAL_CODE_XPOS] = !lookahead[FINAL_CODE_XPOS];
        }
      }
      if (use_bit) {
        imagepos = (imagepos+1) % FINAL_IMAGE.size();
        // Make sure we can't muck this up later.
        for (int i = 0; i < FINAL_CODE.size(); i++)
          if (FINAL_CODE[i] != 'U') lookahead_fixed[i] = true;
      }
    }

    // Maintain a lookahead buffer
    bool actual_ret = lookahead[0];
    for (int i = 0; i+1 < lookahead.size(); i++) {
      lookahead[i] = lookahead[i+1];
      lookahead_fixed[i] = lookahead_fixed[i+1];
    }
    lookahead[lookahead.size()-1] = ret;
    lookahead_fixed[lookahead.size()-1] = retfixed;
    return actual_ret;
  }
};
int Flipper::prob6[64];
string Flipper::block_correlation;
int Flipper::pie_block_index;
vector<int> Flipper::pie_morse_indices;

void Analyze(const string& flips) {
  map<string, int> freq;
  string last = "00000000";
  for (int i = 0; i < flips.size(); i++) {
    last = last.substr(1) + (flips[i]=='T' ? '1' : '0');
    for (int j = 0; j < last.size(); j++) freq[last.substr(j)]++;
  }

  vector<pair<double, pair<string, int> > > v;
  for (int ln = 1; ln <= 7; ln++) {
    cout << endl << ln << "-block relative frequency:" << endl;
    for (map<string, int>::iterator it = freq.begin(); it != freq.end(); ++it)
    if (it->first.size() == ln) {
      double prob = it->second / (double)flips.size() * (1<<ln);
      printf("%s: %.3lf\n", it->first.c_str(), prob);
      if (ln == 7)
        v.push_back(make_pair(prob, make_pair(it->first,
               (it->first[5]-'0') +
             2*(it->first[4]-'0') +
             4*(it->first[3]-'0') +
             8*(it->first[2]-'0') +
            16*(it->first[1]-'0'))));
    }
  }

  sort(v.begin(), v.end());
  cout << endl << "7-blocks sorted by frequency:" << endl;
  for (int i = 0; i < v.size(); i++)
    cout << v[i].first << ": " << v[i].second.first << ' '
         << (char)(v[i].second.second-1+'A') << endl;

  vector<pair<int, int> > vf;
  cout << endl << "Indices with excess 0-1 disparity between "
       << MESSAGE2_BLOCK_SIZE << "-blocks:" << endl;
  for (int i = 0; i < MESSAGE2_BLOCK_SIZE; i++) {
    int n0 = 0, n1 = 0;
    for (int j = i; j < flips.size(); j += MESSAGE2_BLOCK_SIZE)
      if (flips[j] == 'T') n1++; else n0++;
    vf.push_back(make_pair(-abs(n0-n1), i));
  }
  sort(vf.begin(), vf.end());
  for (int i = 0; i < MESSAGE2.size()+10; i++)
    cout << vf[i].second << ": " << -vf[i].first << endl;

  vector<pair<int, int> > vc;
  cout << endl << "Indices with excess correlation between "
       << MESSAGE2_BLOCK_SIZE << "-blocks:" << endl;
  for (int i = 0; i < MESSAGE2_BLOCK_SIZE; i++) {
    int nsame = 0, nswitch = 0;
    for (int j = i+MESSAGE2_BLOCK_SIZE; j < flips.size();
                                        j += MESSAGE2_BLOCK_SIZE)
      if (flips[j] == flips[j-MESSAGE2_BLOCK_SIZE]) nsame++; else nswitch++;
    vc.push_back(make_pair(-abs(nsame-nswitch), i));
  }
  int shift = 0;
  sort(vc.begin(), vc.end());
  for (int i = 0; i < MESSAGE2.size()+10; i++)
    cout << vc[i].second << ": " << -vc[i].first << endl;
  cout << "Message using cutoff of " << -vc[MESSAGE2.size()].first << ":"
       << endl;
  for (int i = 0; i <= MESSAGE2.size(); i++)
    vc[i].first = vc[i].second;
  for(;;) {
    sort(vc.begin(), vc.begin()+MESSAGE2.size()+1);
    if (vc[MESSAGE2.size()].first < MESSAGE2_BLOCK_SIZE-200) break;
    for (int i = 0; i <= MESSAGE2.size(); i++)
      vc[i].first = (vc[i].first+1)%MESSAGE2_BLOCK_SIZE;
    shift++;
  }
  for (int i = 0; i < MESSAGE2.size(); i++) {
    char ch = vc[i+1].first-vc[i].first-1+'A';
    if (ch >= 'A' && ch <= 'Z') cout << ch; else cout << '?';
  }
  cout << endl;

  int piepos = vc[MESSAGE2.size()].first + 1;
  int lastpiece = -1;
  string morse;
  cout << endl << "List of indices into digits of pi, right after message:" << endl;
  for (int i = piepos+MESSAGE2_BLOCK_SIZE-shift;
       i+PI_PIECE_SIZE < flips.size();
       i += MESSAGE2_BLOCK_SIZE) {
    if (morse.size() > FINAL_CODE.size()*20) break;
    char morse_char = '?';
    string s;
    for (int j = 0; j < PI_PIECE_SIZE; j++) s += (flips[i+j]=='T'?'1':'0');
    cout << s << "  ";
    int pos = -1;
    for(;;) {
      pos = PI_DIGS_2.find(s, pos+1);
      if (pos == -1) break;
      if (pos >= lastpiece && pos < lastpiece+20) {
        if (pos-lastpiece == PI_PIECE_SIZE+PI_PIECE_DOT_GAP)
          morse_char = '.';
        else if (pos-lastpiece == PI_PIECE_SIZE+PI_PIECE_DASH_GAP)
          morse_char = '-';
        else if (pos-lastpiece == PI_PIECE_SIZE+PI_PIECE_SPACE_GAP)
          morse_char = ' ';
        else
          morse_char = '?';
        lastpiece = pos;
      }
      cout << ' ' << pos;
    }
    if (morse_char == '?') {
      morse += " ? ";
      lastpiece = PI_DIGS_2.find(s);
    } else {
      morse += morse_char;
    }
    cout << " ->";
    s += (flips[i+PI_PIECE_SIZE]=='T'?'1':'0');
    for(;;) {
      pos = PI_DIGS_2.find(s, pos+1);
      if (pos == -1) break;
      cout << ' ' << pos;
    }
    cout << ' ' << morse_char << endl;
  }
  cout << "Morse code:" << endl;
  cout << morse << endl;
  cout << "Translation:" << endl;
  int pos = morse.find(' ');
  for(;;) {
    int pos2 = morse.find(' ', pos+1);
    if (pos2 == -1) break;
    string s = morse.substr(pos+1, pos2-pos-1);
    char ch = (s.size()==0 ? ' ' : '?');
    for (int i = 0; i < 26; i++) if (MORSE_CODE[i] == s) ch = 'A'+i;
    cout << ch;
    pos = pos2;
  }
  cout << endl;

  cout << endl << "Image formed from pattern " << FINAL_CODE << ":" << endl;
  string image;
  for (int i = 0; i+FINAL_CODE.size() <= flips.size(); i++) {
    bool valid = true;
    char ch;
    for (int j = 0; j < FINAL_CODE.size(); j++) {
      if (FINAL_CODE[j] == 'T' && flips[i+j] != 'T') valid = false;
      if (FINAL_CODE[j] == 'H' && flips[i+j] != 'H') valid = false;
      if (FINAL_CODE[j] == 'X') ch = (flips[i+j]=='T'?'X':'.');
    }
    if (valid) image += ch;
  }
  int X = 23, Y = 13;
  for (int i = 0; i+X*Y < image.size(); i++)
    if (image[i+X*Y] != image[i])
      cout << "WARNING: IMAGE NOT PERIODIC" << endl;
  image = image.substr(0, X*Y);
  for (int i = 0; i <= X*Y; i++) {
    bool border = true;
    for (int x = 0; x < X; x++) if (image[(Y-1)*X+x] != '.') border = false;
    for (int y = 0; y < Y; y++) if (image[y*X] != '.') border = false;
    for (int y = 0; y < Y; y++) if (image[y*X+X-1] != '.') border = false;
    if (border) break;
    if (i == X*Y) cout << "WARNING: IMAGE NOT BORDERED" << endl;
    image = image.substr(1) + image[0];
  }
  for (int y = 0; y < Y; y++) {
    for (int x = 0; x < X; x++) cout << image[y*X+x];
    cout << endl;
  }
}

int main(int argc, char *argv[]) {
  srand(time(0));
  Init();
  Flipper::Precompute();

#ifdef ANALYZER
  // Uncomment this to run the factcheck analysis.
  string flips;
  char ch;
  while (cin >> ch) {
    if (ch=='T' || ch=='H')
      flips += ch;
  }
  Analyze(flips);
#else
  int nflips = (argc < 2) ? 1000000 : atoi(argv[1]);
  Flipper flipper;
  for (int i = 0; i < nflips; i++) {
    cout << (flipper.Flip() ? "T" : "H");
  }
  cout << endl;
#endif

  return 0;
}