p479.ans1
======================
1 2
1 1

=================
p479.ans2
======================
1 2
1 3
1 1

=================
p479.ans3
======================
1 2
3 1
3 3
1 1
1 3
3 2
2 1
2 3
2 2

=================
p479.ans4
======================
No solution

=================
p479.cpp
======================
#include <bits/stdc++.h>

using namespace std;

template<typename T1, typename T2>
ostream& operator<<(ostream& out, const pair<T1, T2>& x) {
    return out << x.first << ' ' << x.second;
}

template<typename T1, typename T2>
istream& operator>>(istream& in, pair<T1, T2>& x) {
    return in >> x.first >> x.second;
}

template<typename T>
istream& operator>>(istream& in, vector<T>& a) {
    for(auto& x: a) {
        in >> x;
    }
    return in;
};

template<typename T>
ostream& operator<<(ostream& out, const vector<T>& a) {
    for(auto x: a) {
        out << x << ' ';
    }
    return out;
};

int n, m;
vector<vector<int>> a;

void read() {
    cin >> n >> m;
    a.assign(n, vector<int>(m));
    cin >> a;
}

void solve() {
    // The core idea here is to think of the process from the end. We know that
    // on the last operation we chose one of the "1"s, so let's try to undo that
    // step. If there was just one it's immediately clear that we can just
    // remove it, and subtract 1 from the neighbors. But what if we have
    // multiple? In that case we can first notice that there can't be two ones
    // that are adjacent to each other - otherwise in the process of "undo"-ing
    // one of them will end up going to negative. If that's not the case, we can
    // just perform all the operations at the same time. While we do this, we
    // should make sure that all non-selected cells so far still remain > 1 even
    // after doing this operation because the problem asks for a solution that
    // covers every cell exactly once.
    //
    // Implementing this naively works in O((N*M)^2), but we can implement it in
    // O(N*M) by keeping a list of positions for every value (5 lists for every
    // value, and keep an iterator in the corresponding list). The complexity is
    // O(N*M) because each move from x -> x-1 can be done in O(1) with list
    // insertions and removals, and the total sum of cells is O(N*M).

    list<pair<int, int>> by_value[6];
    vector<vector<list<pair<int, int>>::iterator>> iters(
        n, vector<list<pair<int, int>>::iterator>(m)
    );
    vector<vector<bool>> done(n, vector<bool>(m, false));

    for(int i = 0; i < n; i++) {
        for(int j = 0; j < m; j++) {
            by_value[a[i][j]].push_back({i, j});
            iters[i][j] = prev(by_value[a[i][j]].end());
        }
    }

    const int dx[] = {-1, 1, 0, 0};
    const int dy[] = {0, 0, -1, 1};

    vector<pair<int, int>> answer;

    while(!by_value[1].empty()) {
        vector<pair<int, int>> ones(by_value[1].begin(), by_value[1].end());

        for(auto [x, y]: ones) {
            for(int d = 0; d < 4; d++) {
                int nx = x + dx[d], ny = y + dy[d];
                if(nx >= 0 && nx < n && ny >= 0 && ny < m && !done[nx][ny] &&
                   a[nx][ny] == 1) {
                    cout << "No solution\n";
                    return;
                }
            }
        }

        map<pair<int, int>, int> decr;
        for(auto [x, y]: ones) {
            for(int d = 0; d < 4; d++) {
                int nx = x + dx[d], ny = y + dy[d];
                if(nx >= 0 && nx < n && ny >= 0 && ny < m && !done[nx][ny]) {
                    decr[{nx, ny}]++;
                }
            }
        }

        for(auto& [pos, cnt]: decr) {
            auto [nx, ny] = pos;
            if(a[nx][ny] - cnt < 1) {
                cout << "No solution\n";
                return;
            }
        }

        for(auto [x, y]: ones) {
            answer.push_back({x, y});
            done[x][y] = true;
            by_value[1].erase(iters[x][y]);
        }

        for(auto& [pos, cnt]: decr) {
            auto [nx, ny] = pos;
            int old_val = a[nx][ny];
            by_value[old_val].erase(iters[nx][ny]);
            a[nx][ny] -= cnt;
            by_value[a[nx][ny]].push_back({nx, ny});
            iters[nx][ny] = prev(by_value[a[nx][ny]].end());
        }
    }

    if((int)answer.size() != n * m) {
        cout << "No solution\n";
        return;
    }

    reverse(answer.begin(), answer.end());
    for(auto [x, y]: answer) {
        cout << x + 1 << ' ' << y + 1 << '\n';
    }
}

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

    int T = 1;
    // cin >> T;
    for(int test = 1; test <= T; test++) {
        read();
        // cout << "Case #" << test << ": ";
        solve();
    }

    return 0;
}

=================
p479.in1
======================
1 2
1 2

=================
p479.in2
======================
1 3
1 3 1

=================
p479.in3
======================
3 3
2 4 2
2 1 2
3 2 3

=================
p479.in4
======================
2 1
1
1

=================
statement.txt
======================
479. Funny Feature
Time limit per test: 0.25 second(s)
Memory limit: 65536 kilobytes
input: standard
output: standard



In the process of preparation to Halloween it was decided to plant some pumpkins on the n × m meters rectangular platform. The platform is divided to n × m identical square cells with 1 meter length sides.

The arrangement of pumpkins was carefully prepared, and you are given the resulting plan. For each cell of this platform it is given how many pumpkins should be planted in it. All these quantities appear to be from 1 to 5, inclusive.

Special pumpkin-landing machine was bought to plant Halloween symbols. It can perform a simple operation: plant pumpkin to the cell, specified by its coordinates (the first coordinate ranges 1 to n, and the second one ranges 1 to m).

At the last moment an unpleasant feature of the machine was discovered. Every time this machine plants a pumpkin to the specified cell, one more pumpkin is also planted to all cells, which are adjacent to the specified one and already have at least one pumpkin in it. One cell is called adjacent to another one if they share a side.

Besides for technical reasons you cannot specify the same cell twice.

Now Halloween celebration is under the threat of failure. You are asked to write the program which finds the sequence of n × m operations leading to demanded landing of pumpkins, or informs that it is impossible.

Input
The first line of input contains two integers n and m  — sizes of the field (1 ≤ n,m ≤ 200). Next n lines contain m integers from 1 to 5  — how many pumpkins should be planted in each cell of the platform. Numbers in lines are separated by single spaces.

Output
If the solution exists, print n × m lines with two numbers in each: a line and a column numbers, where the next pumpkin should be landed. If there are multiple solutions, print any of them.

If the solution does not exist, print a single line "No solution" (quotes for clarity).

Example(s)
sample input
sample output
1 2
1 2
1 2
1 1

sample input
sample output
1 3
1 3 1
1 2
1 3
1 1

sample input
sample output
3 3
2 4 2
2 1 2
3 2 3
1 2
3 1
3 3
1 1
1 3
3 2
2 1
2 3
2 2

sample input
sample output
2 1
1
1
No solution

=================
