1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
#include <bitset>
#include <iostream>
#include <vector>

constexpr int MAX_N = 50000;
constexpr int MAX_M = 2*MAX_N;

enum class OperationType { Sum = 1, And = 2, Neg = 3 };

class Operation {
public:
  OperationType type{};
  int x{};
  int y{};

  Operation(OperationType type, int x, int y): type(type), x(x), y(y) {

  }

  void print() const {
    if(type == OperationType::Neg) {
      std::cout << (int)type << " " << x << "\n";
      return;
    }
    std::cout << (int)type << " " << x << " " << y << "\n";
  }
};


class InputParams {
public:
  int n{};
  int s{};
};

InputParams loadData() {
  InputParams params;
  std::cin >> params.n;
  std::cin >> params.s;
  return params;
}

void addNegOperation(std::bitset<MAX_N>& outSet, std::vector<Operation>& operations, int x) {
  operations.emplace_back(OperationType::Neg, x, 0);
  outSet.flip();
}

void addAndOperation(std::bitset<MAX_N>& outSet, const std::vector<std::bitset<MAX_N>> &sets, std::vector<Operation>& operations, int x, int y) {
  operations.emplace_back(OperationType::And, x, y);
  outSet = outSet & sets[y - 1];
}

void addOrOperation(std::bitset<MAX_N>& outSet, const std::vector<std::bitset<MAX_N>> &sets, std::vector<Operation>& operations, int x, int y) {
  operations.emplace_back(OperationType::Sum, x, y);
  outSet = outSet | sets[y - 1];
}

void fillInitialSets(std::vector<std::bitset<MAX_N>> &sets, const InputParams &params) {
  sets.emplace_back();
  sets[0].set();
  for (int n = 2; n <= params.n; n++) {
    sets.emplace_back();
    std::bitset<MAX_N> &currentSet = sets[n - 1];
    for (int i = n; i <= MAX_N; i += n) {
      currentSet.set(i - 1);
    }
  }
}

void loadTargetSet(std::bitset<MAX_N>& targetSet, const InputParams &params) {
  int x;
  for(int i = 0; i < params.s; i++) {
    std::cin >> x;
    targetSet.set(x - 1);
  }
}

void fillCurrentSet(std::bitset<MAX_N>& currentSet, std::vector<std::bitset<MAX_N>> &sets, const InputParams &params) {
  currentSet = sets[params.n - 1];
}

void fillOperations(std::vector<Operation>& operations, std::bitset<MAX_N>& currentSet, std::bitset<MAX_N>& targetSet, std::vector<std::bitset<MAX_N>> &sets, const InputParams &params) {
  int currentX = params.n;
  bool isFlipped = false;
  for(int i = 0; i < params.n; i++) {
    if(currentSet[i] == targetSet[i]) {
      continue;
    }
    if(currentSet.test(i)) {
      // flip and do sum
      addNegOperation(currentSet, operations, currentX);
      currentX++;
      addOrOperation(currentSet, sets, operations, currentX, i + 1);
      currentX++;
      targetSet.flip();
      isFlipped = !isFlipped;
    } else {
      // do sum
      addOrOperation(currentSet, sets, operations, currentX, i + 1);
      currentX++;
    }
  }
  if(isFlipped) {
    addNegOperation(currentSet, operations, currentX);
  }
}

void printOperations(const std::vector<Operation>& operations) {
  std::cout << operations.size() << "\n";
  for(int i = 0; i < operations.size(); i++) {
    operations[i].print();
  }
}

int main() {
  std::ios_base::sync_with_stdio(false);
  std::cin.tie(nullptr);

  std::vector<std::bitset<MAX_N>> sets;
  sets.reserve(MAX_N);
  std::bitset<MAX_N> targetSet;
  std::bitset<MAX_N> currentSet;

  std::vector<Operation> operations;
  operations.reserve(MAX_M);
  InputParams params = loadData();
  fillInitialSets(sets, params);
  loadTargetSet(targetSet, params);
  fillCurrentSet(currentSet, sets, params);
  fillOperations(operations, currentSet, targetSet, sets, params);
  printOperations(operations);
  return 0;
}