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

struct Result{
    int x;
    int y;
    int size;
};
int n, m;
int minCount;
int colorings = 0;
vector<Result> minRect;


void clear_rect(int*** rect){
    for (int i = 0; i < n; i++)
        for (int j = 0; j < m; j++){
            (*rect)[i][j] = 0;
        }
}
//Проверяем, можно ли вставить квадрат размера size в точку {x,y}
bool isPushable(int** rect, int x, int y, int size){
    if (n-x < size || m-y < size)
        return false;
    for (int i = x; i < x+size; i++)
        for (int j = y; j < y+size; j++){
            if (rect[i][j])
                return false;
        }
    return true;
}

void push(int*** rect, int x, int y, int size){
    for (int i = x; i < x+size; i++)
        for (int j = y; j < y+size; j++){
            (*rect)[i][j] = size;
        }
}

void rec_back(int*** rect, int curSquare, int unPainted, int countOfSquares, vector<Result>* res){
    if (unPainted < curSquare*curSquare)
        return;

    int** _rect = new int*[n];

    for (int i = 0; i < n; i++) {
        _rect[i] = new int[m];
        copy((*rect)[i], (*rect)[i]+m, _rect[i]);
    }

    vector<Result>* _res = new vector<Result>;
    _res->assign(res->begin(), res->end());
    bool pushed = false;
    for (int i = 0; i < n && !pushed; i++){
        for (int j = 0; j < m && !pushed; j++){
            if (_rect[i][j] == 0) {
                if (isPushable(_rect, i, j, curSquare)) {
                    pushed = true;
                    push(&_rect, i, j, curSquare);
                    _res->push_back({i, j, curSquare});
                }
                else
                    return;
            }
            else
                j+=_rect[i][j]-1;
        }
    }

        if (pushed){
            if (countOfSquares+1 == minCount) {
                if (unPainted!=curSquare*curSquare) {
                    return;
                } else {
                    colorings++;
                    return;
                }
            }
            if (unPainted==curSquare*curSquare && countOfSquares+1 < minCount){
                colorings = 1;
                minCount = countOfSquares+1;
                minRect.assign(_res->begin(), _res->end());
                return;
            }
            for (int i = min(min(n,m)-1, max(n,m) - curSquare); i > 0; i--)
                rec_back(&_rect, i, unPainted-curSquare*curSquare, countOfSquares+1, _res);
        }
        else {
            for (int i = curSquare-1; i > 0; i--)
                rec_back(&_rect, i, unPainted, countOfSquares, _res);
        }

    for (int i = 0; i < n; i++) {
        delete _rect[i];
    }
    delete[] _rect;
    delete _res;
}

int main() {
    cout << "Enter rectangle height&width: ";
    cin >> n >> m;
    minCount = n*m;
    int** rect = new int*[n];
    for (int i = 0; i < n; i++)
        rect[i] = new int[m];
    clear_rect(&rect);
    vector<Result> vec;
    for (int i = min(n,m)-1; i > 0; i--)
        rec_back(&rect, i, n*m, 0, &vec);
    cout << "Minimal number of squares: " << minCount << endl;
    for (auto i = minRect.begin(); i != minRect.end(); i++){
        cout << i->x << ' ' << i->y << ' ' << i->size << '\n';
    }
    cout << "\nCount of minimal permutations: " << colorings << endl;
    return 0;
}