#include <bits/stdc++.h>

using namespace std;

// #define LOCK_GETCHAR
// #define USE_INT_128

#if __cplusplus < 201400
#warning "Please use c++14 or higher."
#define CONSTEXPR_FUNC
#define ENABLE_IF_INT
#else
#define CONSTEXPR_FUNC constexpr
#define ENABLE_IF_INT , enable_if_t<_is_integer<T>, int> = 0
template <class T> constexpr bool _is_integer = numeric_limits<T>::is_integer;
template <> constexpr bool _is_integer<bool> = false;
template <> constexpr bool _is_integer<char> = false;
#ifdef USE_INT_128
template <> constexpr bool _is_integer<__int128> = true;
template <> constexpr bool _is_integer<__uint128_t> = true;
#endif
template <class T ENABLE_IF_INT>
constexpr T INF = numeric_limits<T>::max() >> 1;
#endif

#if !defined(_WIN32) && !defined(LOCK_GETCHAR)
#define getchar getchar_unlocked
#endif

#define il inline
#define mkp make_pair
#define fi first
#define se second
#define For(i, j, k) for (decltype(j - k) i = (j); i <= (k); ++i)     // NOLINT
#define ForDown(i, j, k) for (decltype(j - k) i = (j); i >= (k); --i) // NOLINT
#define pb push_back
#define eb emplace_back
#ifndef ONLINE_JUDGE
#define FileIO(filename)                                                       \
  freopen(filename ".in", "r", stdin);                                         \
  freopen(filename ".out", "w", stdout)
#else
#define FileIO(filename) void(0)
#endif

using ll = long long;
using uint = unsigned int;
using ull = unsigned long long;
using db = double;
using ldb = long double;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
#ifdef USE_INT_128
using lll = __int128_t;
using ulll = __uint128_t;
#endif

// clang-format off
#define lg(x) (31 ^ __builtin_clz((x)))
#define lgll(x) (31ll ^ __builtin_clzll((x)))
template<typename T> constexpr il T sq(const T & x){ return x * x; }
template<typename T> CONSTEXPR_FUNC il void cmin(T & x, const T &y){ x = min(x, y); }
template<typename T> CONSTEXPR_FUNC il void cmax(T & x, const T &y){ x = max(x, y);}
template<typename T> CONSTEXPR_FUNC il T qpow(T x, ull y, T mod){T ans = 1; x %= mod; while (y) { if(y & 1)(ans *= x) %= mod;(x *= x) %= mod; y >>= 1;} return ans;}
template<typename T> CONSTEXPR_FUNC il T qpow(T x, ull y){T ans = 1; while (y) {if(y & 1) ans *= x;x *= x;y >>= 1;} return ans;}
template<typename T ENABLE_IF_INT> il void read(T &x){ x = 0; int f = 1; int c = getchar(); while(!isdigit(c)) {if (c == '-') f = -1;c = getchar();} while(isdigit(c)) {x = x * 10 + c - '0';c = getchar();} x *= f;}
template<typename T, typename ... Args> il void read(T &x, Args &... y){ read(x); read(y...); }
int gcd(int a, int b) { if (!a | !b) return a + b; int az = __builtin_ctz(a); int bz = __builtin_ctz(b); int z = min(az, bz); a >>= az, b >>= bz; while (a != b) { int diff = b - a; az = __builtin_ctz(diff); b = min(a, b), a = abs(diff) >> az; } return a << z; }
ll gcd(ll a, ll b) { if (!a | !b) return a + b; ll az = __builtin_ctzll(a); ll bz = __builtin_ctzll(b); ll z = min(az, bz); a >>= az, b >>= bz; while (a != b) { ll diff = b - a; az = __builtin_ctzll(diff); b = min(a, b), a = abs(diff) >> az; } return a << z; }
// clang-format on

// File head end

constexpr int ZERO_BIT = -1, ONE_BIT = -2;
vector<tuple<int, int, int>> Gates;
int cnt = 0;
struct Bit {
  int _id;
  Bit(int _ = ZERO_BIT) : _id(_) {}
  bool known() const { return _id == ZERO_BIT || _id == ONE_BIT; }
  bool val() const {
    assert(this->known());
    return _id == ONE_BIT;
  }
  Bit operator&(const Bit &rhs) const {
    if (_id == ZERO_BIT || rhs._id == ZERO_BIT)
      return ZERO_BIT;
    else if (_id == ONE_BIT || rhs._id == ONE_BIT)
      return (_id == ONE_BIT) ? rhs._id : _id;
    Gates.eb(_id, rhs._id, 8);
    return ++cnt;
  }
  Bit operator|(const Bit &rhs) const {
    if (_id == ONE_BIT || rhs._id == ONE_BIT)
      return 1;
    else if (_id == ZERO_BIT || rhs._id == ZERO_BIT)
      return (_id == ZERO_BIT) ? rhs._id : _id;
    Gates.eb(_id, rhs._id, 14);
    return ++cnt;
  }
  Bit operator^(const Bit &rhs) const {
    if (_id == ZERO_BIT || rhs._id == ZERO_BIT)
      return _id == ZERO_BIT ? rhs._id : _id;
    else if (_id == ONE_BIT || rhs._id == ONE_BIT)
      return _id == ONE_BIT ? ~rhs : ~*this;
    Gates.eb(_id, rhs._id, 6);
    return ++cnt;
  }
  Bit operator~() const {
    if (_id == ZERO_BIT)
      return ONE_BIT;
    else if (_id == ONE_BIT)
      return ZERO_BIT;
    Gates.eb(_id, 1, 5);
    return ++cnt;
  }
  Bit operator==(const Bit &rhs) const {
    if (this->known() && rhs.known())
      return (this->val() == rhs.val()) ? ONE_BIT : ZERO_BIT;
    Gates.eb(_id, rhs._id, 9);
    return ++cnt;
  }
};
struct Ushort {
  array<Bit, 16> bits;
  Ushort() = default;
  Ushort(Bit x) { bits[0] = x; }
  Ushort operator+(const Ushort &rhs) const {
    Ushort res;
    Bit carry;
    For(i, 0, 15) {
      auto tmp = bits[i] ^ rhs.bits[i];
      res.bits[i] = tmp ^ carry;
      if (i < 15)
        carry = (bits[i] & rhs.bits[i]) | (carry & tmp);
    }
    return res;
  }
  Ushort check(Bit x) const {
    Ushort ans;
    For(i, 0, 15) ans.bits[i] = bits[i] & x;
    return ans;
  }
};

#define _Find(x)                                                               \
  (lower_bound(names2.begin(), names2.end(), (x)) - names2.begin())

int alice(const int n, const char names[][5], const unsigned short numbers[],
          bool outputs_alice[]) {
  assert(n <= 30);
  vector<pair<string, unsigned short>> names2(n);
  For(i, 0, n - 1) names2[i] = {names[i], numbers[i]};
  sort(names2.begin(), names2.end());
  int len = n * 16 + n * 5;
  For(i, 0, n - 1) {
    For(j, i * 16, i * 16 + 15) {
      outputs_alice[j] = (names2[i].se >> (j - i * 16)) & 1;
    }
  }
  For(i, 0, n - 1) {
    int id = _Find(mkp(string(names[i]), numbers[i]));
    // cerr << "A " << i << ' ' << id << '\n';
    For(j, i * 5, i * 5 + 4) {
      outputs_alice[n * 16 + j] = (id >> (j - i * 5)) & 1;
      // cerr << outputs_alice[n * 16 + j];
    }
    // cerr << '\n';
  }
  return len;
}
int bob(const int m, const char senders[][5], const char recipients[][5],
        bool outputs_bob[]) {
  vector<string> names2;
  For(i, 0, m - 1) names2.eb(senders[i]), names2.eb(recipients[i]);
  sort(names2.begin(), names2.end());
  names2.erase(unique(names2.begin(), names2.end()), names2.end());
  int n = names2.size(), len = n * n;
  For(i, 0, m - 1) {
    int u = _Find(senders[i]);
    int v = _Find(recipients[i]);
    outputs_bob[u * n + v] = 1;
  }
  return len;
}

int circuit(const int la, const int lb, int operations[], int operands[][2],
            int outputs_circuit[][16]) {
  Gates.clear(), cnt = la + lb + 1;
  operands[la + lb][0] = 0, operands[la + lb][1] = 0,
                operations[la + lb] = 0; // zero
  operands[la + lb + 1][0] = 0, operands[la + lb + 1][1] = 0,
                     operations[la + lb + 1] = 15; // one
  int n = la / 21;
  cerr << "C " << n << '\n';
  vector<Ushort> ans(n), real_ans(n), num(n);
  For(i, 0, n - 1) For(j, 0, 15) num[i].bits[j] = i * 16 + j;

  cerr << "C " << Gates.size() << '\n';

  For(u, 0, n - 1) For(v, 0, n - 1) {
    ans[v] = ans[v] + num[u].check(Bit(la + u * n + v));
  }

  auto trans = [&](int x) {
    array<Bit, 5> ans;
    For(i, 0, 4) ans[i] = (x >> i & 1) ? ONE_BIT : ZERO_BIT;
    return ans;
  };
  auto op_equ = [&](const array<Bit, 5> &x, const array<Bit, 5> &y) {
    Bit res = ONE_BIT;
    For(i, 0, 4) res = res & (x[i] == y[i]);
    return res;
  };
  For(i, 0, n - 1) {
    array<Bit, 5> cur1, cur2;
    For(j, 0, 4) cur1[j] = n * 16 + i * 5 + j;
    For(j, 0, n - 1) {
      cur2 = trans(j);
      real_ans[i] = real_ans[i] + ans[j].check(op_equ(cur1, cur2));
    }
  }

  auto _To_final = [&](int x) {
    return (x == ZERO_BIT) ? la + lb : (x == ONE_BIT ? la + lb + 1 : x);
  };
  cnt = la + lb + 2;
  cerr << "C " << Gates.size() << '\n';
  for (auto [u, v, f] : Gates) {
    u = _To_final(u), v = _To_final(v);
    operations[cnt] = f, operands[cnt][0] = u, operands[cnt][1] = v;
    cnt++;
  }
  For(i, 0, n - 1) For(j, 0, 15) outputs_circuit[i][j] =
      _To_final(real_ans[i].bits[j]._id);
  return cnt;
}