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



//Структура заполненного квадрата в виде координаты-размер квадрата
struct Result{
    int x;
    int y;
    int size;
};

int n, m;
int minCount;
int colorings = 0;
vector<Result> minRect;


//Функция инициализации прямоугольника нулями
void ClearRect(vector<vector<int>> &rect){
    for (int i = 0; i < n; i++) {
        rect.resize(n);
        for (int j = 0; j < m; j++) {
            rect[i].push_back(0);
        }
    }
}

void printRect(vector<vector<int>>& _rect){

    cout << "\t===>>\n";
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            cout.width(3);
            cout << _rect[i][j];
        }
        cout << '\n';
    }
    cout << endl;
}

//Функция восстановления прямоугольника и вектора вставленных квадратов
void recovery(vector<vector<int>>& _rect, vector<Result> &_res){
    Result temp = *(_res.rbegin());
    _res.pop_back();
    for (int i = temp.x; i < temp.x+temp.size; i++)
        for (int j = temp.y; j < temp.y+temp.size; j++)
            _rect[i][j] = 0;
}

//Функция проверки на то, можно ли вставить квадрат размера size в точку {x,y}
bool isPushable(vector<vector<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(vector<vector<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(vector<vector<int>>& _rect, int curSquare, int UnPaint, int countOfSquares, vector<Result> &_res){
    if ((countOfSquares==minCount-1 && UnPaint > curSquare*curSquare))
        return;

    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);
#ifdef DBG
                    printRect(_rect);
#endif
                    _res.push_back({i, j, curSquare});
                }
                else{
                    return;
                }
            }
            else
                j+=_rect[i][j]-1;
        }
    }

    if (countOfSquares+1 == minCount) {
        if (UnPaint==curSquare*curSquare)
            colorings++;
        recovery(_rect, _res);
        return;
    }
    if (UnPaint==curSquare*curSquare && countOfSquares+1 < minCount){
        colorings = 1;
        minCount = countOfSquares+1;
        minRect.assign(_res.begin(), _res.end());
        recovery(_rect, _res);
        return;
    }

    for (int i = min(min(n,m)-1, max(n,m) - curSquare); i > 0; i--)
        if (i*i <= UnPaint)
            rec_back(_rect, i, UnPaint-curSquare*curSquare, countOfSquares+1, _res);

    recovery(_rect, _res);
}

int main() {
    cout << "Enter rectangle height & width: ";
    cin >> n >> m;
    minCount = n*m+1;
    int scalingCoef = 1;
    vector<vector<int>> rect;
    vector<Result> preLoad;

    if (n==m){
        if (n%2 == 0){
            scalingCoef = n/2;
            n = 2;
            m = 2;
        }
        else if (n%3 == 0){
            scalingCoef = n/3;
            n = 3;
            m = 3;
        }
        else if (n%5 == 0){
            scalingCoef = n/5;
            n = 5;
            m = 5;
        }
    }

    ClearRect(rect);
    int UnPaint = n*m;

    for (int i = min(n,m)-1; i > 0; i--)
        rec_back(rect, i, UnPaint, preLoad.size(), preLoad);

    cout << "Minimal number of squares: " << minCount << endl;
    for (auto & i : minRect){
        cout << scalingCoef*i.x + 1 << ' ' << scalingCoef*i.y + 1 << ' ' << scalingCoef*i.size << '\n';
    }
    cout << "\nCount of minimal permutations: " << colorings << endl;
    return 0;

}