#include <cassert>
#include <cmath>
#include <cstdint>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <functional>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>

using namespace std;

using Int = long long;

template <class T1, class T2> ostream &operator<<(ostream &os, const pair<T1, T2> &a) { return os << "(" << a.first << ", " << a.second << ")"; };
template <class T> ostream &operator<<(ostream &os, const vector<T> &as) { const int sz = as.size(); os << "["; for (int i = 0; i < sz; ++i) { if (i >= 256) { os << ", ..."; break; } if (i > 0) { os << ", "; } os << as[i]; } return os << "]"; }
template <class T> void pv(T a, T b) { for (T i = a; i != b; ++i) cerr << *i << " "; cerr << endl; }
template <class T> bool chmin(T &t, const T &f) { if (t > f) { t = f; return true; } return false; }
template <class T> bool chmax(T &t, const T &f) { if (t < f) { t = f; return true; } return false; }


int mix(int x) {
  x = (20230705LL * x) % 1'000'000'403;
  return x;
}

constexpr int E = 30;
constexpr int F = 11;
constexpr int GP = 5;
constexpr int GM = 7;
constexpr int M0 = 150;

string toBinary(int len, int x) {
  string s(len, '?');
  for (int e = 0; e < len; ++e) s[e] = "01"[x >> e & 1];
  return s;
}
int fromBinary(const string &s) {
  const int len = s.size();
  int x = 0;
  for (int e = 0; e < len; ++e) x |= (s[e] - '0') << e;
  return x;
}

string encode(int N, const vector<int> &X, const vector<int> &Y) {
  string S;
  
  int P;
  vector<int> H(N);
  for (int a = 0; a < 1 << GP; ++a) {
    P = (1 << F) - 1 - a;
    for (int i = 0; i < N; ++i) {
      H[i] = mix(X[i]) % P;
    }
    if ((int)set<int>(H.begin(), H.end()).size() == N) {
cerr<<"perfect a = "<<a<<", P = "<<P<<endl;
      S += toBinary(GP, a);
      goto foundPerfect;
    }
  }
  assert(false);
 foundPerfect:{}
  
  int minCost = 1001001001;
  int am = -1;
  for (int a = 0; a < 1 << GM; ++a) {
    const int M = M0 + a;
    vector<int> freq(M);
    for (int i = 0; i < N; ++i) {
      ++freq[H[i] % M];
    }
    int cost = M;
    for (int m = 0; m < M; ++m) {
      cost += F * max(freq[m] - 1, 0);
    }
cerr<<"M = "<<M<<": cost = "<<cost<<endl;
    if (chmin(minCost, cost)) {
      am = a;
    }
  }
  const int M = M0 + am;
  S += toBinary(GM, am);
  
  vector<vector<pair<int, int>>> hiss(M);
  for (int i = 0; i < N; ++i) {
    hiss[H[i] % M].emplace_back(H[i], i);
  }
  for (int m = 0; m < M; ++m) {
    auto &his = hiss[m];
    sort(his.begin(), his.end());
  }
// cerr<<"hiss = "<<hiss<<endl;
  for (int m = 0; m < M; ++m) {
    const auto &his = hiss[m];
    for (const auto &hi : his) {
      const int i = hi.second;
      S += toBinary(E, Y[i]);
    }
  }
  for (int m = 0; m < M; ++m) {
    const auto &his = hiss[m];
    S += (!his.empty()) ? '1' : '0';
  }
  for (int m = 0; m < M; ++m) {
    const auto &his = hiss[m];
    for (int j = 1; j < (int)his.size(); ++j) {
      S += toBinary(F, his[j].first);
    }
  }
  return S;
}

vector<int> decode(int N, int Q, int K, const string &S, const vector<int> &Z) {
  int P, M;
  map<int, int> mapa, nazo;
  {
    int cur = 0;
    P = (1 << F) - 1 - fromBinary(S.substr(cur, GP)); cur += GP;
    const int am = fromBinary(S.substr(cur, GM)); cur += GM;
    M = M0 + am;
    vector<int> Y(N);
    for (int i = 0; i < N; ++i) {
      Y[i] = fromBinary(S.substr(cur, E)); cur += E;
    }
    vector<vector<int>> hss(M);
    for (int m = 0; m < M; ++m) {
      const char any = S[cur++];
      if (any != '0') {
        hss[m].push_back(-1);
      }
    }
    for (; cur < K; ) {
      const int h = fromBinary(S.substr(cur, F)); cur += F;
      hss[h % M].push_back(h);
    }
// cerr<<"hss = "<<hss<<endl;
    {
      int i = 0;
      for (int m = 0; m < M; ++m) {
        for (const int h : hss[m]) {
          const int y = Y[i++];
          if (~h) {
            mapa[h] = y;
          } else {
            nazo[m] = y;
          }
        }
      }
    }
    assert(cur == K);
  }
  vector<int> ans(Q);
  for (int q = 0; q < Q; ++q) {
    const int h = mix(Z[q]) % P;
    auto it = mapa.find(h);
    if (it != mapa.end()) {
      ans[q] = it->second;
    } else {
      ans[q] = nazo[h % M];
    }
  }
  return ans;
}

int main() {
  int T;
  scanf("%d", &T);
  if (T == 1) {
    int N;
    scanf("%d", &N);
    vector<int> X(N), Y(N);
    for (int i = 0; i < N; ++i) {
      scanf("%d%d", &X[i], &Y[i]);
    }
    const string S = encode(N, X, Y);
    const int K = S.size();
    printf("%d\n", K);
    puts(S.c_str());
  } else {
    int N, Q, K;
    scanf("%d%d%d", &N, &Q, &K);
    char buf[6010];
    scanf("%s", buf);
    const string S = buf;
    vector<int> Z(Q);
    for (int q = 0; q < Q; ++q) {
      scanf("%d", &Z[q]);
    }
    const auto ans = decode(N, Q, K, S, Z);
    for (int q = 0; q < Q; ++q) {
      printf("%d\n", ans[q]);
    }
  }
  return 0;
}