#include <bits/stdc++.h>

using namespace std;
using ll = long long;

string encode(vector<int> a, int b) {
    if (size(a) == 0) {
        return {};
    }
    if (size(a) <= 1) {
        string s;
        while (b > 0) {
            s += '0' + bool(a[0] & b);
            b /= 2;
        }
        return s;
    }
    assert(b > 0);
    int mid = 0;
    while (mid < size(a) && !(a[mid] & b)) {
        mid += 1;
    }
    string ans;
    int h = __lg(size(a)) + 1;
    for (int i = 0; i < h; ++i) {
        ans += '0' + (mid >> i & 1);
    }
    string l = encode(vector(a.begin(), a.begin() + mid), b / 2);
    string r = encode(vector(a.begin() + mid, a.end()), b / 2);
    return ans + l + r;
}

void decode(vector<int> &ans, int &p, int n, const string &s, int b, int up) {
    if (n == 0) {
        return;
    }
    if (n == 1) {
        while (b > 0) {
            up += (s[p++] - '0') * b;
            b /= 2;
        }
        return ans.push_back(up);
    }
    int h = __lg(n) + 1;
    int mid = 0;
    for (int i = 0; i < h; ++i) {
        if (s[p++] == '1') {
            mid += 1 << i;
        }
    }
    decode(ans, p, mid, s, b / 2, up);
    decode(ans, p, n - mid, s, b / 2, up + b);
}

string encodePerm(const vector<int> &p) {
    int n = size(p);
    string s;
    vector<bool> used(n);
    for (int i = 0; i < n - 1; ++i) {
        int f = find(p.begin(), p.end(), i) - p.begin();
        int pos = count(used.begin(), used.begin() + f, false);
        used[f] = true;
        int h = __lg(n - i);
        for (int k = 0; k < h; ++k) {
            s += '0' + (pos >> k & 1);
        }
    }
    return s;
}

vector<int> decodePerm(int n, const string &s) {
    vector<int> p(n, -1);
    int pnt = 0;
    for (int i = 0; i < n - 1; ++i) {
        int h = __lg(n - i);
        int pos = 0;
        for (int k = 0; k < h; ++k) {
            pos += (s[pnt++] - '0') << k;
        }
        for (int j = 0; j < n; ++j) {
            if (p[j] == -1 && pos-- == 0) {
                p[j] = i;
                break;
            }
        }
    }
    p[find(p.begin(), p.end(), -1) - p.begin()] = n - 1;
    return p;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    constexpr int A = 1e9 + 1;

    int type;
    cin >> type;

    mt19937 rnd(1337);

    if (type == 1) {
        int n;
        cin >> n;

        map<int, int> mp;
        vector<int> x(n), y(n);

        for (int i = 0; i < n; ++i) {
            int a, b;
            cin >> a >> b;
            int xr = rnd() % A;
            a ^= xr, b ^= xr;
            mp[a] = b;
            x[i] = a, y[i] = b;
        }

        sort(x.begin(), x.end());
        sort(y.begin(), y.end());

        assert(unique(x.begin(), x.end()) == x.end());
        assert(unique(y.begin(), y.end()) == y.end());

        string ex = encode(x, 1 << 29);
        string ey = encode(y, 1 << 29);
        vector<int> p(n);
        for (int i = 0; i < n; ++i) {
            p[i] = lower_bound(y.begin(), y.end(), mp[x[i]]) - y.begin();
        }
        string ep = encodePerm(p);

//        for (int t = 0; t < 3; ++t) {
//            for (int i = 0; i < 12; ++i) {
//                cout << (size(t == 0 ? ex : t == 1 ? ey : ep) >> i & 1);
//            }
//        }
        cout << size(ex + ey + ep) << '\n';
        cout << ex << ey << ep << '\n';
    } else {
        int n, q, k;
        cin >> n >> q >> k;

        vector<int> xr(n);

        for (int i = 0; i < n; ++i) {
            xr[i] = rnd() % A;
        }

        string s;
        cin >> s;

        vector<int> x, y, p;
        int i = 0;

        decode(x, i, n, s, 1 << 29, 0);
        decode(y, i, n, s, 1 << 29, 0);
        p = decodePerm(n, s.substr(i));

        for (int qwq = 0; qwq < q; ++qwq) {
            int a;
            cin >> a;
            for (int r : xr) {
                int j = lower_bound(x.begin(), x.end(), a ^ r) - x.begin();
                if (j < n && (x[j] ^ r) == a) {
                    cout << (y[p[j]] ^ r) << '\n';
                    break;
                }
            }
        }
    }

    return 0;
}