IPSC2017_K

#include <iostream>
#include <cassert>
using namespace std;

#define SZ 28
char s[1000001],bits[4000001];
int p[1 << SZ];

void proc(){
    cin >> s;
    int t = 0;
    for (int i = 0; s[i]; i++) {
        int x = ((int)s[i] - 33);
        int d = x % 3; x /= 3;
        int c = x % 3; x /= 3;
        int b = x % 3; x /= 3;
        int a = x % 3; x /= 3;
        bits[t++] = a;
        bits[t++] = b;
        bits[t++] = c;
        bits[t++] = d;
        //      cout << a << b << c << d;
    }
    int last = -1, pat=0;
    for (int i = 0; i<t; i++) {
        if (bits[i] == 2) {
            last = i; pat = 0;
        }
        else {
            //counting if 0 or 1 is more likely given `pat`
            if (i > last + SZ) {
                if (bits[i]) {
                    if (p[pat] == -1) p[pat] = 1;
                    else p[pat]++;
                }
                else {
                    if (p[pat] == 0) p[pat] = -2;
                    else if (p[pat] == 1) p[pat] = -1;
                    else p[pat]--;
                }
            }
            pat = (pat * 2 + bits[i])&((1 << SZ) - 1);
            assert(pat >= 0 && pat < (1 << SZ));
        }
    }
    pat = 0;
    for (int i = 0; i < t; i++) {
        if (bits[i] == 2) {
            int x = 0;
            if (p[pat] > 0) x = 1;
            if (p[pat] == 0) cerr << "ouch " << i << endl;
            if (i < SZ) cerr << "interesting " << i << endl;
            bits[i] = x;
            cout << x;
        }
        pat = (pat * 2 + bits[i])&((1 << SZ) - 1);
        assert(pat >= 0 && pat < (1 << SZ));
    }
    cout << endl;
}

int main() {
    cerr << "one" << endl;
    proc();
    cerr << "two" << endl;
    proc();
    return 0;

}