#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
#define MASK(i) (1ULL << (i))
#define GETBIT(mask, i) (((mask) >> (i)) & 1)
#define ALL(v) (v).begin(), (v).end()
ll max(ll a, ll b){return (a > b) ? a : b;}
ll min(ll a, ll b){return (a < b) ? a : b;}
ll gcd(ll a, ll b){return __gcd(abs(a), abs(b));}
ll lcm(ll a, ll b){return abs(a) / gcd(a, b) * abs(b);}
ll LASTBIT(ll mask){return (mask) & (-mask);}
int pop_cnt(ull mask){return __builtin_popcountll(mask);}
int ctz(ull mask){return __builtin_ctzll(mask);}
int logOf(ull mask){return 63 - __builtin_clzll(mask);}
template <class T1, class T2>
bool maximize(T1 &a, T2 b){
if (a < b) {a = b; return true;}
return false;
}
template <class T1, class T2>
bool minimize(T1 &a, T2 b){
if (a > b) {a = b; return true;}
return false;
}
template <class T>
void printArr(T container, string separator = " ", string finish = "\n", ostream &out = cout){
for(auto item: container) out << item << separator;
out << finish;
}
template <class T>
void remove_dup(vector<T> &a){
sort(ALL(a));
a.resize(unique(ALL(a)) - a.begin());
}
#include "abc.h"
const int OP_ZERO = 0; // f(OP_ZERO, x0, x1) = 0
const int OP_NOR = 1; // f(OP_NOR, x0, x1) = !(x0 || x1)
const int OP_GREATER = 2; // f(OP_GREATER, x0, x1) = (x0 > x1)
const int OP_NOT_X1 = 3; // f(OP_NOT_X1, x0, x1) = !x1
const int OP_LESS = 4; // f(OP_LESS, x0, x1) = (x0 < x1)
const int OP_NOT_X0 = 5; // f(OP_NOT_X0, x0, x1) = !x0
const int OP_XOR = 6; // f(OP_XOR, x0, x1) = (x0 ^ x1)
const int OP_NAND = 7; // f(OP_NAND, x0, x1) = !(x0 && x1)
const int OP_AND = 8; // f(OP_AND, x0, x1) = (x0 && x1)
const int OP_EQUAL = 9; // f(OP_EQUAL, x0, x1) = (x0 == x1)
const int OP_X0 = 10; // f(OP_X0, x0, x1) = x0
const int OP_GEQ = 11; // f(OP_GEQ, x0, x1) = (x0 >= x1)
const int OP_X1 = 12; // f(OP_X1, x0, x1) = x1
const int OP_LEQ = 13; // f(OP_LEQ, x0, x1) = (x0 <= x1)
const int OP_OR = 14; // f(OP_OR, x0, x1) = (x0 || x1)
const int OP_ONE = 15; // f(OP_ONE, x0, x1) = 1
int encode(string s){
int ans = 0;
int po = 1;
for(int i = 1; i < (int) s.size(); ++i){
ans += po *= 26;
}
for(int i = 0; i < (int) s.size(); ++i){
ans += po * (s[i] - 'a');
po /= 26;
}
return ans;
}
int alice(const int n, const char names[][5], const unsigned short numbers[], bool outputs_alice[]) {
vector<string> namek;
for(int i = 0; i < n; ++i){
namek.emplace_back();
for(int j =0; j < 5; ++j){
if (names[i][j] == '\0') break;
namek.back().push_back(names[i][j]);
}
}
int idx = 0;
for(int i = 0; i < n; ++i){
int x = encode(namek[i]);
for(int j = 0; j < 19; ++j) {
outputs_alice[idx++] = GETBIT(x, j);
}
for(int j = 0; j < 16; ++j) {
outputs_alice[idx++] = GETBIT(numbers[i], j);
}
}
return idx;
}
int bob(const int m,const char senders[][5],const char recipients[][5],bool outputs_bob[]) {
vector<string> senders_name;
for(int i = 0; i < m; ++i){
senders_name.emplace_back();
for(int j =0; j < 5; ++j){
if (senders[i][j] == '\0') break;
senders_name.back().push_back(senders[i][j]);
}
}
vector<string> recipients_name;
for(int i = 0; i < m; ++i){
recipients_name.emplace_back();
for(int j =0; j < 5; ++j){
if (recipients[i][j] == '\0') break;
recipients_name.back().push_back(recipients[i][j]);
}
}
int idx = 0;
for(int i = 0; i < m; ++i){
int x = encode(senders_name[i]);
int y = encode(recipients_name[i]);
for(int j = 0; j < 19; ++j) {
outputs_bob[idx++] = GETBIT(x, j);
}
for(int j = 0; j < 19; ++j){
outputs_bob[idx++] = GETBIT(y, j);
}
}
return idx;
}
struct LogicGate{
int x, y, type;
LogicGate(int x = -1, int y = -1, int type = -1): x(x), y(y), type(type){}
};
vector<LogicGate> gay;
int create_new_gate(int x, int y, int OP){
gay.emplace_back(LogicGate(x, y, OP));
return gay.size() - 1;
}
vector<int> op_add(vector<int> x, int y, int off_set = 0){ // op_add(x[], y, offset) = x + (y << offset)
for(int it = off_set; it < (int) x.size(); ++it){
int i = x[it];
int j = create_new_gate(i, y, OP_XOR);
int k = create_new_gate(i, y, OP_AND);
x[it] = j;
y = k;
}
return x;
}
vector<int> op_add(vector<int> x, vector<int> y){ // op_add(x[], y[]) = x[] + y[]
if (x.size() < y.size()) swap(x, y);
for(int i = 0; i < (int) y.size(); ++i){
x = op_add(x, y[i], i);
}
return x;
}
vector<int> op_xor(vector<int> x, vector<int> y){ // op_add(x[], y[]) = x[] ^ y[]
if (x.size() != y.size()) assert(false);
for(int i = 0; i < (int) x.size(); ++i){
x[i] = create_new_gate(x[i], y[i], OP_XOR);
}
return x;
}
vector<int> op_multiply(vector<int> x, vector<int> y){ // op_multiply(x[], y[]) = x[] * y[]
vector<int> ans;
for(int i = 0; i < (int) x.size(); ++i){
ans.push_back(gay.size());
}
gay.push_back(LogicGate(0, 0, OP_ZERO));
for(int i = 0; i < (int) y.size(); ++i)
for(int j = 0; j < (int) x.size(); ++j){
if (i + j < (int)x.size()){
int k = gay.size();
gay.push_back(LogicGate(y[i], x[j], OP_AND));
ans = op_add(ans, k, i + j);
}
}
return ans;
}
int op_equal(vector<int> x, vector<int> y){ // op_equal(x[], y[]) -> (x == y)
if (x.size() != y.size()) assert(false);
vector<int> z(x.size());
for(int i = 0; i < (int) x.size(); ++i){
z[i] = create_new_gate(x[i], y[i], OP_EQUAL);
}
int ans = z[0];
for(int i = 1; i < (int) z.size(); ++i){
ans = create_new_gate(ans, z[i], OP_AND);
}
return ans;
}
vector<int> op_equal_multiply(vector<int> x, vector<int> y, vector<int> z){ // op_equal(x[], y[], z[]) -> (x == y) * z
if (x.size() != y.size()) assert(false);
int t = op_equal(x, y);
vector<int> ans = z;
for(int &i: ans){
i = create_new_gate(i, t, OP_AND);
}
return ans;
}
int circuit(const int la, const int lb, int operations[],int operands[][2],int outputs_circuit[][16]) {
int n = la / 35, m = lb / 38;
gay.reserve(2e7);
for(int i = 0; i < la + lb; ++i) gay.emplace_back();
int CACHE_ZERO = create_new_gate(0, 0, OP_ZERO);
vector<vector<int>> names(n), favorite_number(n);
for(int i = 0; i < n; ++i){
for(int j = 0; j < 19; ++j) names[i].push_back(i * 35 + j);
for(int j = 19; j < 35; ++j) favorite_number[i].push_back(i * 35 + j);
}
vector<vector<int>> ans(n);
for(int i = 0; i < n; ++i){
ans[i].resize(16, CACHE_ZERO);
}
for(int i = 0; i < m; ++i){
vector<int> u, v;
for(int j = 0; j < 19; ++j) u.push_back(la + i * 38 + j);
for(int j = 19; j < 38; ++j) v.push_back(la + i * 38 + j);
vector<int> sender_favorite_number;
for(int j = 0; j < n; ++j){
vector<int> cur = op_equal_multiply(u, names[j], favorite_number[j]);
if (sender_favorite_number.empty()) sender_favorite_number = cur;
else{
sender_favorite_number = op_xor(sender_favorite_number, cur);
}
}
for(int j = 0; j < n; ++j){
vector<int> cur = op_equal_multiply(v, names[j], sender_favorite_number);
ans[j] = op_add(ans[j], cur);
}
}
for(int i = la + lb; i < (int)gay.size(); ++i){
operations[i] = gay[i].type;
operands[i][0] = gay[i].x;
operands[i][1] = gay[i].y;
}
for(int i = 0; i < n; ++i) for(int j = 0; j < 16; ++j){
outputs_circuit[i][j] = ans[i][j];
}
return gay.size();
}
