1772F - Copy of a Copy of a Copy - CodeForces Solution

#include<bits/stdc++.h>
using namespace std;

// #include<ext/pb_ds/assoc_container.hpp>
// #include<ext/pb_ds/tree_policy.hpp>
// using namespace __gnu_pbds;
// #define ordered_set tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update>

typedef long long ll;
typedef vector<ll> vi;
typedef vector<vector<ll>> vvi;
typedef long double ld;
typedef pair<ll, ll> pii;
const int mod = ll(1e9)+7; const ll inf = ll(1e15); const ll minf  = -inf;

#define forw(x, i) for(auto it= x.begin(); it!= x.end(); it++)
#define backw(x, i) for(auto it= x.rbegin(); it!= x.rend(); it++)
#define rep(i, x, n) for(ll i=x; i < n; i++)
#define mp(x, y) make_pair(x, y)
#define pb(x) push_back(x)
#define sp(x) setprecision(x)
#define all(x) x.begin(), x.end()
#define sz(x) ll(x.size())
#define int long long
#define yes cout << "YES" << "\n";
#define no cout << "NO" << "\n";
#define fe first
#define se second
#ifndef ONLINE_JUDGE
#define debug(a) cerr << #a <<": "; _print(a); cerr << "\n";
#else
#define debug(a) // no more tle
#endif

#ifndef ONLINE_JUDGE
#define nline cerr << "\n";
#else
#define nline // no more tle
#endif


void init_code() {
#ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
    freopen("error.txt", "w", stderr);
#endif
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
}

void _print(int64_t t) { cerr << t;}
void _print(int32_t t) { cerr << t;}
void _print(string t) { cerr << t;}
void _print(char t) { cerr << t;}
void _print(ld t) { cerr << t;}
void _print(double t) { cerr << t;}

template<class T, class V> void _print(pair<T, V> p);
template<class T, class V> void _print(map<T, V> p);
template<class T> void _print(vector<T> p);
template<class T> void _print(set<T> p);
template<class T> void _print(multiset<T> p);

template<class T, class V> void _print(pair<T, V> p) { cerr << "{"; _print(p.fe); cerr << ","; _print(p.se); cerr << "}";}
template<class T, class V> void _print(map<T, V> p) {cerr << "["; for (auto i : p) {_print(i); cerr << ' ';} cerr << "]"; }
template<class T> void _print(vector<T> p) { cerr << "["; for (T i : p) {_print(i); cerr << ' ';} cerr << "]"; }
template<class T> void _print(set<T> p) { cerr << "["; for (T i : p) {_print(i); cerr << ' ';} cerr << "]"; }
template<class T> void _print(multiset<T> p) { cerr << "["; for (T i : p) {_print(i); cerr << ' ';} cerr << "]"; }

int powermod(int a, int b) {if (b == 0) return 1;   int temp = powermod(a, b / 2);  temp = (temp * temp) % mod; if (b & 1) temp = (temp * a) % mod; return temp;}
int power(int a, int b) {int res = 1; while (b > 0) {if (b & 1) {   res = res * a; b--;} else {a = a * a; b = b / 2;}} return res;}
ll mod_inv(int a) { return powermod(a, mod - 2);}
int lcm(int a, int b) { return (a*b)/__gcd(a, b); }




void solve() {
    int n, m, k;
    cin >> n >> m >> k;
    map<vvi, vector<int>> cnt;
    map<int, vvi> lol;
    vector<vector<int>> v;
    v.resize(n, vector<int> (m));
    int indx = 1;
    int max_change=0;
    rep(i, 0, k+1) {
        for(int r=0; r < n; r++) {
            for(int c=0; c<m; c++) {
                char d;
                cin >> d;
                v[r][c] = d-'0';
            }
        }
        int x=0;
        for(int r=1; r < n-1; r++) {
            for(int c=1; c < m-1; c++) {
                set<int> st;
                st.insert(v[r+1][c]);
                st.insert(v[r-1][c]);
                st.insert(v[r][c+1]);
                st.insert(v[r][c-1]);
                if(st.size() == 1 and *st.begin() == (!v[r][c])) x++;
            }
        }
        lol[x] = v;
        cnt[v].pb(i+1);
        if(x > max_change) {
            indx= i+1; max_change= x;
        }
    }


    // starting matrix is the one with maximum x
    vector<vector<int>> cur = lol.rbegin()->se;
    vector<vector<int>> ans;
    cout << indx << "\n"; // start indx
    backw(lol, it) {
        vector<vector<int>> target = it->se;
        rep(i, 1, n-1) {
            rep(j, 1, m-1) {
                if(target[i][j]!= cur[i][j]) {
                    ans.push_back({1, i+1, j+1});
                }
            }
        }
        vector<int> occurences = cnt[target];
        for(int i : occurences) {
            if(i == indx) continue;
            ans.push_back({2, i});
        }
        cur= target;
    }
    cout << sz(ans) << "\n";
    for(vector<int> & a : ans) {
        for(int i : a) cout << i <<' ';
            cout << "\n";
    }
    return; 
}




int32_t main() {
   init_code();
   bool test = 0;
   if (test) { int t; cin >> t; while (t--) solve(); }
   else { solve(); }
   return 0;
}