SquaringSquares

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

// Класс для представления квадрата
class Square {
public:
    int x, y, size;
    Square(int x, int y, int size) : x(x), y(y), size(size) {}
};

// Глобальные переменные
int n;
int min_squares;
vector<Square> best_solution;
vector<int> required_squares; // список размеров обязательных квадратов

// Функция для проверки, занято ли место на доске
bool is_taken(const vector<Square>& table, int x, int y) {
    for (const auto& square : table) {
        if (square.x <= x && x < square.x + square.size && square.y <= y && y < square.y + square.size) {
            return true;
        }
    }
    return false;
}

// Функция для выполнения бэктрекинга
void solve(vector<Square> table, int current_area, int square_count, int min_x, int min_y) {
    for (int x = min_x; x < n; ++x) {
        for (int y = min_y; y < n; ++y) {
            if (!is_taken(table, x, y)) {
                int limit = min(n - x, n - y);
                for (const auto& square : table) {
                    if (square.x + square.size > x && square.y > y) {
                        limit = min(limit, square.y - y);
                    }
                }
                for (int size = limit; size > 0; --size) {
                    Square square(x, y, size);
                    vector<Square> currTable = table;
                    currTable.push_back(square);
                    if (current_area + size * size == n * n) {
                        if (square_count + 1 < min_squares) {
                            min_squares = square_count + 1;
                            best_solution = currTable;
                        }
                    }
                    else if (square_count + 1 < min_squares) {
                        solve(currTable, current_area + size * size, square_count + 1, x, y + size);
                    }
                }
                return;
            }
        }
        min_y = 0;
    }
}

int main() {
    // Ввод размера доски
    cin >> n;

    int m;
    // Ввод количества обязательных квадратов
    cin >> m;
    required_squares.resize(m);

    // Ввод обязательных квадратов
    for (int i = 0; i < m; ++i) {
        cin >> required_squares[i];
    }

    if (n % 2 != 0) {
        // Если размер нечетный, выполняем бэктрекинг для нахождения лучшего покрытия
        min_squares = 2 * n + 1; // максимально возможное количество квадратов
        best_solution.clear();
        int size_of_table = 1;

        // Поиск наибольшего делителя
        for (int i = 2; i < n; ++i) {
            if (n % i == 0) {
                size_of_table = i;
            }
        }
        n /= size_of_table;

        // Начальное состояние таблицы с обязательными квадратами
        vector<Square> startTable;
        int current_area = 0;

        for (int size : required_squares) {
            Square sq(0, 0, size);
            startTable.push_back(sq);
            current_area += size * size;
        }

        // Добавление начальных квадратов, если площадь не заполнена обязательными квадратами
        if (current_area < n * n) {
            int extra_squares = (n * n - current_area) / ((n + 1) / 2 * (n + 1) / 2);
            for (int i = 0; i < extra_squares; ++i) {
                startTable.push_back(Square(0, 0, (n + 1) / 2));
            }
        }

        // Запуск бэктрекинга
        solve(startTable, current_area, startTable.size(), 0, 0);

        // Вывод результата
        cout << best_solution.size() << endl;
        for (const auto& square : best_solution) {
            cout << square.x * size_of_table << " " << square.y * size_of_table << " " << square.size * size_of_table << endl;
        }
    } else {
        // Если размер четный, выводим фиксированное покрытие
        cout << 4 << endl;
        cout << 0 << " " << 0 << " " << n / 2 << endl;
        cout << 0 << " " << n / 2 << " " << n / 2 << endl;
        cout << n / 2 << " " << 0 << " " << n / 2 << endl;
        cout << n / 2 << " " << n / 2 << " " << n / 2 << endl;
    }

    return 0;
}