#include <iostream>
#include <iomanip>
#include <vector>
#include <cmath>
#include <algorithm>
#include <map>
#include <numeric>
#include <deque>
#include <set>
#include <functional>
#include <queue>
#include <fstream>
#include <string>
#include <random>
#include <sstream>
#include <thread>

using namespace std;
const int mod = 998244353;
int64_t binpow(int64_t a, int64_t b) {
    int64_t r = 1;
    while (b) {
        if (b & 1) r = (r * a) % mod;
        a = (a * a) % mod;
        b >>= 1;
    }
    return r;
}
unordered_map<int, int> factorize(int n) {
    unordered_map<int, int> res;
    for (int i = 2; i * i <= n; ++i) {
        while (!(n % i)) n /= i, res[i]++;
    }
    if (n != 1) res[n]++;
    return res;
}
const int Y = 17;
string solve1(const string& cs) {
    string s = cs;
    if (s.size() == 1) {
        return s + s + s;
    }
    for (auto& e : s) e -= '0';
    vector<int> ind(s.size());
    iota(ind.begin(), ind.end(), 0);
    vector<int> a1, a2;
    vector<int> add;
    int c = 0;
    for (int i = 1; i <= Y; ++i) {
        int w = 1 << i;
        a1.clear();
        a2.clear();
        for (int j = 0; j < s.size(); ++j) {
            if (j % w >= w / 2) a1.push_back(j);
            else a2.push_back(j);
        }
        c = 0;
        if (a1.size() < a2.size()) swap(a1, a2);
        for (auto& e : a1) c ^= s[e];
        add.push_back(c);
    }
    for (auto& e : add) s.push_back(e);
    for (auto& e : s) e += '0';
    return s;
}

string solve2(const string& ss) {
    if (ss.size() == 3) {
        if (ss[0] == ss[1]) return string() + ss[0];
        return string() + ss[2];
    }
    int n = ss.size() - Y;
    string s = ss;
    for (auto& e : s) e -= '0';

    bool was = 0;
    int c = 0;
    for (int i = 0; i < n; ++i) c ^= s[i];
    int save = c;
    vector<int> ind(n);
    iota(ind.begin(), ind.end(), 0);
    set<int> ok(ind.begin(), ind.end());
    vector<int> a1, a2;
    int pos = n;
    int cnt_neq = 0;
    auto foo = [&]() {
        for (int i = 1; i <= Y; ++i) {
            int w = 1 << i;
            a1.clear();
            a2.clear();
            for (int j = 0; j < n; ++j) {
                if (j % w >= w / 2) a1.push_back(j);
                else a2.push_back(j);
            }
            if (a1.size() < a2.size()) swap(a1, a2);
            c = 0;
            for (auto& e : a1) c ^= s[e];
            if (c == s[pos]) {
                for (auto& e : a1) ok.erase(e);
            }
            else {
                cnt_neq = i;
                for (auto& e : a2) ok.erase(e);
            }
            ++pos;
        }
        };
    foo();
    if (cnt_neq && ok.size()) {
        int ps = *ok.begin();
        s[n + cnt_neq - 1] ^= 1;
        cnt_neq = 0;
        pos = n;
        foo();
        if (cnt_neq) {
            s[ps] ^= 1;
        }
    }
    for (auto& e : s) e += '0';
    return s.substr(0, n);
}
mt19937 gen(12412);
vector<int> ww(20);
void gn(int l, int r, int d = 1) {
    if (l >= r) return;
    ww[d]++;
    gn(l, (l + r) / 2, d + 1);
    gn(1 + (l + r) / 2, r, d + 1);
}
int main(int argc, char* argv[]) {
    /*ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);*/
    gn(1, 1e5);
    while (1) {
        int l = 1e5;
        string s;
        for (int i = 0; i < l; ++i) s.push_back('0' + (rand() & 1));
        auto r1 = solve1(s);
        auto rr2 = r1;
        rr2[gen() % (rr2.size())] ^= 1;
        auto r2 = solve2(rr2);
        cout << rr2.size() << "\n";
        if (r2 != s) {
            solve2(rr2);
            return -1;
        }
    }
    int t;
    cin >> t;
    if (t == 1) {
        string s; cin >> s;
        cout << solve1(s) << "\n";
    }
    else {
        string s;
        cin >> s;
        cout << solve2(s) << "\n";
    }
}