#include <bits/stdc++.h>
#include "registers.h"
using namespace std;
template <typename A, typename B>
string to_string(pair<A, B> p);
template <typename A, typename B, typename C>
string to_string(tuple<A, B, C> p);
template <typename A, typename B, typename C, typename D>
string to_string(tuple<A, B, C, D> p);
string to_string(const string& s) {
return '"' + s + '"';
}
string to_string(const char* s) {
return to_string((string) s);
}
string to_string(bool b) {
return (b ? "true" : "false");
}
string to_string(vector<bool> v) {
bool first = true;
string res = "{";
for (int i = 0; i < static_cast<int>(v.size()); i++) {
if (!first) {
res += ", ";
}
first = false;
res += to_string(v[i]);
}
res += "}";
return res;
}
template <size_t N>
string to_string(bitset<N> v) {
string res = "";
for (size_t i = 0; i < N; i++) {
res += static_cast<char>('0' + v[i]);
}
return res;
}
template <typename A>
string to_string(A v) {
bool first = true;
string res = "{";
for (const auto &x : v) {
if (!first) {
res += ", ";
}
first = false;
res += to_string(x);
}
res += "}";
return res;
}
template <typename A, typename B>
string to_string(pair<A, B> p) {
return "(" + to_string(p.first) + ", " + to_string(p.second) + ")";
}
template <typename A, typename B, typename C>
string to_string(tuple<A, B, C> p) {
return "(" + to_string(get<0>(p)) + ", " + to_string(get<1>(p)) + ", " + to_string(get<2>(p)) + ")";
}
template <typename A, typename B, typename C, typename D>
string to_string(tuple<A, B, C, D> p) {
return "(" + to_string(get<0>(p)) + ", " + to_string(get<1>(p)) + ", " + to_string(get<2>(p)) + ", " + to_string(get<3>(p)) + ")";
}
void debug_out() { cerr << endl; }
template <typename Head, typename... Tail>
void debug_out(Head H, Tail... T) {
cerr << " " << to_string(H);
debug_out(T...);
}
#define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__);
const int b = 2000;
const int m = 100;
vector<bitset<b>> r(m);
int cnt = 0;
vector<int> to_vec(int id, int n, int k) {
vector<int> a(n);
for (int i = 0; i < n * k; i++) {
a[i / k] += r[id][i] << (i % k);
}
return a;
}
void Printf(int n, int k, int id) {
vector<int> a = to_vec(id, n, k);
cerr << "{";
for (int i = 0; i < n; i++) {
if (i != 0) cerr << " ";
cerr << a[i];
if (i != n - 1) cerr << ",";
}
cerr << "}";
cerr << endl;
}
void append_move(int t, int y) {}
void append_store(int t, vector<bool> v) {}
void append_and(int t, int x, int y) {}
void append_or(int t, int x, int y) {}
void append_xor(int t, int x, int y) {}
void append_not(int t, int x) {}
void append_left(int t, int x, int p) {}
void append_right(int t, int x, int p) {}
void append_add(int t, int x, int y) {}
int so_far = 0;
void Move(int t, int y) {
r[t] = r[y];
so_far++;
}
int Store(vector<bool> v) {
so_far++;
int t = cnt++;
assert(int(v.size()) == b);
append_store(t, v);
for (int i = 0; i < b; i++) r[t][i] = v[i];
return t;
}
int And(int x, int y) {
so_far++;
int t = cnt++;
append_and(t, x, y);
r[t] = r[x] & r[y];
return t;
}
int Or(int x, int y) {
so_far++;
int t = cnt++;
append_or(t, x, y);
r[t] = r[x] | r[y];
return t;
}
int Xor(int x, int y) {
so_far++;
int t = cnt++;
append_xor(t, x, y);
r[t] = r[x] ^ r[y];
return t;
}
int Not(int x) {
so_far++;
int t = cnt++;
append_not(t, x);
for (int i = 0; i < b; i++) r[t][i] = r[x][i] ? 0 : 1;
return t;
}
int Shift_left(int x, int p) {
so_far++;
int t = cnt++;
append_left(t, x, p);
r[t] = r[x] << p;
return t;
}
int Shift_right(int x, int p) {
so_far++;
int t = cnt++;
append_right(t, x, p);
r[t] = r[x] >> p;
return t;
}
int Add(int x, int y) {
so_far++;
int t = cnt++;
append_add(t, x, y);
int carries = 0;
for (int i = 0; i < b; i++) {
int sum = r[x][i] + r[y][i] + carries;
r[t][i] = sum % 2;
carries = sum / 2;
}
return t;
}
struct Bitset {
int id = -1;
Bitset(int _id) : id(_id) {};
Bitset operator-() const { return Bitset(Not(id)); };
Bitset operator>>(int p) { return Bitset(Shift_right(id, p)); };
Bitset operator<<(int p) { return Bitset(Shift_left(id, p)); };
void operator=(const Bitset &a) { Move(id, a.id); };
};
Bitset operator+(const Bitset &lhs, const Bitset &rhs) { return Bitset(Add(lhs.id, rhs.id)) ;}
Bitset operator^(const Bitset &lhs, const Bitset &rhs) { return Bitset(Xor(lhs.id, rhs.id)) ;}
Bitset operator|(const Bitset &lhs, const Bitset &rhs) { return Bitset(Or(lhs.id, rhs.id)) ;}
Bitset operator&(const Bitset &lhs, const Bitset &rhs) { return Bitset(And(lhs.id, rhs.id)) ;}
Bitset Store(const function<bool(const int&)> &f) {
vector<bool> bits(b);
for (int i = 0; i < b; i++) bits[i] = f(i);
return Bitset(Store(bits));
}
int N, K;
void debug_out(Bitset a) {
Printf(N, K, a.id);
}
void construct_instructions(int s, int n, int k, int q) {
N = n, K = k;
Bitset a = Bitset(0);
cnt++;
Bitset Full = Store([&](int i) {
return true;
});
Bitset One = Store([&](int i) {
return i == 0;
});
int reset_register = cnt;
auto Lesser_greater = [&](Bitset Even_skipped_blocks, Bitset Odd_skipped_blocks, int total_blocks) {
assert(total_blocks & 1);
Bitset Full_even_indexes = Store([&](int i) {
int block_id = i / k;
if (block_id >= total_blocks) return false;
if (block_id & 1) return false;
return true;
});
Bitset Header_remainder_even_blocks = Store([&](int i) {
int block_id = i / k;
if (block_id >= total_blocks + 1) return false;
if (i % (2 * k) == k) return true;
return false;
});
Bitset Even_plus_full_minus_odd = Even_skipped_blocks + (Full_even_indexes ^ Odd_skipped_blocks);
Bitset Greater_even_blocks_head = Even_plus_full_minus_odd & Header_remainder_even_blocks;
Bitset Full_greater_even_blocks = Greater_even_blocks_head + (Full ^ Greater_even_blocks_head >> k) + One;
Bitset Full_not_less_odd_blocks = Full_greater_even_blocks ^ Full_even_indexes;
Bitset Greater_skipped = (Even_skipped_blocks & Full_greater_even_blocks) ^ (Odd_skipped_blocks & Full_not_less_odd_blocks);
Bitset Lesser_skipped = Even_skipped_blocks ^ Odd_skipped_blocks ^ Greater_skipped;
Bitset ret = Lesser_skipped ^ (Greater_skipped << k);
return ret;
};
auto E_O_switch = [&]() {
Bitset Even_skipped_blocks = a & Store([&](int i) {
if (i >= n * k) return false;
int block_id = i / k;
return block_id % 2 == 0;
});
Bitset Odd_skipped_blocks = (a & Store([&](int i) {
if (i >= n * k) return false;
int block_id = i / k;
return block_id % 2 == 1;
})) >> k;
int last_even_block_id = n - 1 - (n & 1 ^ 1);
int last_odd_block_id = n - 1 - (n & 1);
int total_block = last_even_block_id + 1;
if (last_odd_block_id != total_block) Odd_skipped_blocks = Odd_skipped_blocks | Store([&](int i) {
int L = (total_block - 1) * k, R = L + k - 1;
return L <= i && i <= R;
});
a = Lesser_greater(Even_skipped_blocks, Odd_skipped_blocks, total_block);
if (last_odd_block_id != total_block) a = a ^ Store([&](int i) {
int L = total_block * k + k, R = L + k - 1;
return L <= i && i <= R;
});
cnt = reset_register;
};
auto O_E_switch = [&]() {
if (n <= 2) return;
Bitset Even_skipped_blocks = (a & Store([&](int i) {
if (i >= n * k) return false;
int block_id = i / k;
return block_id % 2 == 0;
})) >> (k << 1);
Bitset Odd_skipped_blocks = (a & Store([&](int i) {
if (i >= n * k) return false;
int block_id = i / k;
return block_id % 2 == 1;
})) >> k;
int last_even_block_id = n - 1 - (n & 1 ^ 1);
int last_odd_block_id = n - 1 - (n & 1);
int total_block = last_odd_block_id;
if (last_even_block_id != total_block + 1) Even_skipped_blocks = Even_skipped_blocks | Store([&](int i) {
int L = (total_block - 1) * k, R = L + k - 1;
return L <= i && i <= R;
});
Bitset first_block = a & Store([&](int i) {
return i < k;
});
a = Lesser_greater(Odd_skipped_blocks, Even_skipped_blocks, total_block) << k | first_block;
if (last_odd_block_id != total_block) a = a ^ Store([&](int i) {
int L = (total_block + 1) * k + k, R = L + k - 1;
return L <= i && i <= R;
});
cnt = reset_register;
};
if (s == 1) {
int beg = 0;
int iter = n;
while (iter--) {
if (!beg & 1) {
E_O_switch();
} else {
O_E_switch();
}
beg ^= 1;
}
assert(so_far <= q);
} else {
Bitset Full_even_indexes = Store([&](int i) {
int block_id = i / k;
if (block_id & 1) return false;
return true;
});
Bitset Header_remainder_even_blocks = Store([&](int i) {
if (i % (2 * k) == k) return true;
return false;
});
auto Lesser = [&](Bitset Even_skipped_blocks, Bitset Odd_skipped_blocks) {
Bitset Even_plus_full_minus_odd = Even_skipped_blocks + (Full_even_indexes ^ Odd_skipped_blocks);
Bitset Greater_even_blocks_head = Even_plus_full_minus_odd & Header_remainder_even_blocks;
Bitset Full_greater_even_blocks = Greater_even_blocks_head + (Full ^ Greater_even_blocks_head >> k) + One;
Bitset Full_not_less_odd_blocks = Full_greater_even_blocks ^ Full_even_indexes;
Bitset Lesser_skipped = (Even_skipped_blocks & Full_not_less_odd_blocks) ^ (Odd_skipped_blocks & Full_greater_even_blocks);
return Lesser_skipped;
};
a = a | Store([&](int i) {
return n * k <= i;
});
Bitset Even_skipped_blocks = a & Full_even_indexes;
Bitset Odd_skipped_blocks = (a & Full_even_indexes << k) >> k;
Bitset Lesser_skipped = Lesser(Even_skipped_blocks, Odd_skipped_blocks);
int Log = 1;
while ((1 << Log) - 1 < n - 1) {
Lesser_skipped = Lesser(Lesser_skipped, Lesser_skipped >> (k << Log));
Log++;
}
a = Lesser_skipped;
}
assert(so_far <= q);
}
