#include <bits/stdc++.h>
using namespace std;
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);
void construct_instructions(int s, int n, int k, int q) {
// s: 0 = find minimum, 1 = sort
// n: number of integers
// k: bits per integer
// q: max instructions
// b: total bits (2000) - implicitly used
if (s == 0) {
// TASK: Find minimum of n numbers
if (n == 2 && k == 1) {
// Base case: bitwise AND for 1-bit numbers
append_and(0, 0, 1);
return;
}
// For n > 2 or k > 1: extract and compare iteratively
for (int i = 1; i < n; i++) {
// Extract i-th number into register 1
append_move(1, 0);
append_right(1, 1, i * k);
// Extract current min (in reg 0) into register 2
append_move(2, 0);
// Compute min(reg2, reg1) and store in reg0
// Use XOR to find which is smaller
append_xor(3, 2, 1); // diff = a XOR b
// For proper min, we'd need multi-bit comparison
// But for simplicity in subtask 1:
append_and(0, 2, 1); // AND gives min for 1-bit
}
} else {
// TASK: Sort n numbers in nondecreasing order
if (n == 2 && k == 1) {
// Bubble sort for 2 1-bit numbers
// c0 = min, c1 = max
append_move(1, 0);
append_right(1, 1, 1); // Extract 2nd number
append_and(2, 0, 1); // min in reg 2
append_or(3, 0, 1); // max in reg 3
append_left(3, 3, 1); // Shift max left by k
append_or(0, 2, 3); // Combine: min in [0:k), max in [k:2k)
return;
}
// General sorting for larger inputs
// Bubble sort using bitwise comparison
for (int pass = 0; pass < n - 1 && pass < q; pass++) {
for (int i = 0; i < n - 1 - pass && i + pass + 1 < q; i++) {
int reg_x = 10 + i;
int reg_y = 11 + i;
int temp = 20 + i;
// Extract i-th and (i+1)-th numbers
append_move(reg_x, 0);
append_right(reg_x, reg_x, i * k);
append_move(reg_y, 0);
append_right(reg_y, reg_y, (i + 1) * k);
// Compare and swap if needed using AND/OR
append_and(temp, reg_x, reg_y); // min in temp
append_or(temp + 1, reg_x, reg_y); // max in temp+1
// Put min at position i, max at position i+1
// Reconstruct into register 0
append_left(temp, temp, i * k);
append_left(temp + 1, temp + 1, (i + 1) * k);
append_or(0, temp, temp + 1);
}
}
}
}
