#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<int,pair<int,int>>> V;
for(int i=0; i<n; i++)
{
for(int j=0; j<m; j++)
{
V.push_back({X[i][j],{i,j}});
}
}
// cout << "here" << endl;
sort(V.begin(), V.end());
vector<pair<vector<int>,vector<int>>> V2(n);
ll ans=0LL;
ll mid = V[int((n*m)/2)].ff;
for(int i=0; i<int((n*m)/2); i++)
{
V2[V[i].ss.ff].ff.push_back(V[i].ss.ss);
ans += abs(mid - V[i].ff);
}
for(int i=int((n*m)/2); i<n*m; i++)
{
V2[V[i].ss.ff].ss.push_back(V[i].ss.ss);
ans += abs(mid - V[i].ff);
}
// cout << "here" << endl;
for(int round=0; round<k; round++)
{
int mins=0;
int maxes=0;
// cout << "here" << endl;
for(int i=0; i<n; i++)
{
if(round == k-1)
{
// cout << V2[i].ff.size() << " " << V2[i].ss.size() << " ayeet" << endl;
// cout << V2[i].ss.back() << endl;
}
if(V2[i].ff.empty())
{
// cout << V2[i].ss.back() << endl;
maxes++;
answer[i][V2[i].ss.back()]=round;
V2[i].ss.pop_back();
continue;
}
if(V2[i].ss.empty())
{
mins++;
answer[i][V2[i].ff.back()]=round;
V2[i].ff.pop_back();
}
}
// cout << len(V2[0].ff) << " " << len(V2[0].ss) << endl;
for(int i=0; i<n; i++)
{
if(V2[i].ff.empty() || V2[i].ss.empty()) continue;
if(maxes < int(n/2))
{
maxes++;
answer[i][V2[i].ss.back()]=round;
V2[i].ss.pop_back();
}
else
{
mins++;
answer[i][V2[i].ff.back()]=round;
V2[i].ff.pop_back();
}
}
}
// cout << ans << endl;
allocate_tickets(answer);
return ans; // min(no_zeroes, n*m-no_zeroes);
}
#ifdef ARTHUR_LOCAL
int main()
{
find_maximum(3, {{1,1,1},{1,1,1}});
}
#endif
