#include <bits/stdc++.h>
using namespace std;
#ifndef ARTHUR_LOCAL
#include "tickets.h"
#endif
using ll = long long;
#define len(x) int((x).size())
#define ff first
#define ss second
#ifdef ARTHUR_LOCAL
void allocate_tickets(vector<vector<int>> ans)
{
for(auto a:ans)
{
for(auto b:a) cout << b << " ";
cout << endl;
}
}
#endif
ll find_maximum(int k, vector<vector<int>> X)
{
int n = len(X);
int m = len(X[0]);
vector<vector<int>> answer;
for (int i = 0; i < n; i++)
{
vector<int> row(m);
for(int j = 0; j < m; j++)
{
row[j] = -1;
}
answer.push_back(row);
}
vector<pair<vector<int>,vector<int>>> V;
int no_zeroes = 0;
for(int i=0; i<n; i++)
{
for(int j=0; j<m; j++)
{
if(X[i][j] == 0) no_zeroes++;
}
}
int dom=-1;
if(no_zeroes + no_zeroes >= n*m) dom = 0;
else dom=1;
for(int i=0; i<n; i++)
{
pair<vector<int>,vector<int>> P = {{},{}};
for(int j=0; j<m; j++)
{
if(X[i][j] == dom) P.ss.push_back(j);
else P.ff.push_back(j);
}
V.push_back(P);
}
ll cur_ans = 0LL;
for(int round=0; round<k; round++)
{
int doms=0;
int nondoms=0;
for(int i=0; i<n; i++)
{
if(V[i].ss.empty())
{
nondoms++;
cout << i << " " << V[i].ff.back() << " 1" << endl;
answer[i][V[i].ff.back()]=round;
V[i].ff.pop_back();
continue;
}
if(V[i].ff.empty())
{
doms++;
cout << i << " " << V[i].ss.back() << " 2" << endl;
answer[i][V[i].ss.back()]=round;
V[i].ss.pop_back();
continue;
}
}
for(int i=0; i<n; i++)
{
if(V[i].ff.empty() || V[i].ss.empty()) continue;
if(nondoms < int(n/2))
{
nondoms++;
cout << i << " " << V[i].ff.back() << " 3" << endl;
answer[i][V[i].ff.back()]=round;
V[i].ff.pop_back();
continue;
}
else
{
doms++;
cout << i << " " << V[i].ss.back() << " 4" << endl;
answer[i][V[i].ss.back()]=round;
V[i].ss.pop_back();
continue;
}
}
cur_ans += min(doms,nondoms);
}
allocate_tickets(answer);
return cur_ans; // min(no_zeroes, n*m-no_zeroes);
}
#ifdef ARTHUR_LOCAL
int main()
{
find_maximum(2, {{0,1},{0,1}});
}
#endif
