#pragma optimize("Bismillahirrahmanirrahim")
//█▀█─█──█──█▀█─█─█
//█▄█─█──█──█▄█─█■█
//█─█─█▄─█▄─█─█─█─█
//Allahuekber
//ahmet23 orz...
//Sani buyuk Osman Pasa Plevneden cikmam diyor.
//FatihSultanMehmedHan
//YavuzSultanSelimHan
//AbdulhamidHan
#define author tolbi
#include <bits/stdc++.h>
using namespace std;
template<typename X, typename Y> istream& operator>>(istream& in, pair<X,Y> &pr) {return in>>pr.first>>pr.second;}
template<typename X, typename Y> ostream& operator<<(ostream& os, pair<X,Y> pr) {return os<<pr.first<<" "<<pr.second;}
template<typename X> istream& operator>>(istream& in, vector<X> &arr) {for(auto &it : arr) in>>it; return in;}
template<typename X> ostream& operator<<(ostream& os, vector<X> arr) {for(auto &it : arr) os<<it<<" "; return os;}
template<typename X, size_t Y> istream& operator>>(istream& in, array<X,Y> &arr) {for(auto &it : arr) in>>it; return in;}
template<typename X, size_t Y> ostream& operator<<(ostream& os, array<X,Y> arr) {for(auto &it : arr) os<<it<<" "; return os;}
template<typename T> vector<int32_t> normalize(vector<T> &arr){vector<int32_t> rv;rv.resize(arr.size());for (long long i = 0; i < rv.size(); ++i){rv[i]=arr[i];}return rv;}
#define endl '\n'
#define vint(x) vector<int> x
#define deci(x) int x;cin>>x;
#define decstr(x) string x;cin>>x;
#define cinarr(x) for (auto &it : x) cin>>it;
#define coutarr(x) for (auto &it : x) cout<<it<<" ";cout<<endl;
#define sortarr(x) sort(x.begin(),x.end())
#define sortrarr(x) sort(x.rbegin(),x.rend())
#define det(x) cout<<"NO\0YES"+x*3<<endl;
#define INF LONG_MAX
#define rev(x) reverse(x.begin(),x.end());
#define ios ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define tol(bi) (1LL<<((int)(bi)))
const int MOD = 1e9+7;
mt19937 ayahya(chrono::high_resolution_clock().now().time_since_epoch().count());
typedef long long ll;
#include "tickets.h"
long long find_maximum(int32_t k, vector<vector<int32_t>> _arr) {
int n = _arr.size();
int m = _arr[0].size();
vector<vector<ll>> arr(n,vector<ll>(m));
for (int i = 0; i < n; i++){
for (int j = 0; j < m; j++){
arr[i][j]=_arr[i][j];
}
}
int hed = k*((n+1)/2);
vector<vector<ll>> dp(n,vector<ll>(hed+1,-1));
vector<vector<ll>> pref = arr;
vector<vector<ll>> suff = arr;
for (int i = 0; i < n; i++){
for (int j = 1; j < m; j++){
pref[i][j]+=pref[i][j-1];
}
for (int j = m-2; j >= 0; j--){
suff[i][j]+=suff[i][j+1];
}
}
function<ll(int,int)> bastan = [&](int i, int j){
if (j==0) return 0ll;
return pref[i][j-1];
};
function<ll(int,int)> sondan = [&](int i, int j){
if (j==0) return 0ll;
return suff[i][m-j];
};
function<ll(int,int)> f;
vector<vector<int>> way(n,vector<int>(hed+1,-1));
f = [&](int node, int flag)->ll{
if (node==n) {
if (flag) return -23;
return 0;
}
if (dp[node][flag]!=-1) return dp[node][flag];
dp[node][flag]=-23;
for (int i = 0; i <= min(k,flag); i++){
if (f(node+1,flag-i)==-23) continue;
ll crr = f(node+1,flag-i)+(sondan(node,k-i)-bastan(node,i));
if (crr>dp[node][flag]){
dp[node][flag]=crr;
way[node][flag]=i;
}
}
return dp[node][flag];
};
vector<vector<int>> rval(n,vector<int>(m,-1));
ll ans = f(0,hed);
vector<int> crr(n);
for (int node = 0; node < n; node++){
crr[node]=way[node][hed];
hed-=way[node][hed];
}
vector<int> kucuk(k,n/2);
vector<int> buyuk(k,n/2);
set<int> avak;
set<int> avab;
for (int i = 0; i < k; ++i)
{
avak.insert(i);
avab.insert(i);
}
for (int i = 0; i < n; i++){
set<int> kul;
for (int j = 0; j < crr[i]; j++){
rval[i][j]=*avak.begin();
kul.insert(rval[i][j]);
avak.erase(avak.begin());
}
set<int> kul2;
while (kul.size()){
kul2.insert(*kul.begin());
int node = *kul.begin();
kul.erase(node);
kucuk[node]--;
if (kucuk[node]>0) avak.insert(node);
}
set<int> kul3;
for (int j = m-1; j >= m-(k-crr[i]); j--){
while (kul2.find(*avab.begin())!=kul2.end()){
kul3.insert(*avab.begin());
avab.erase(avab.begin());
}
rval[i][j]=*avab.begin();
kul.insert(rval[i][j]);
avab.erase(avab.begin());
}
while (kul.size()){
int node = *kul.begin();
kul.erase(node);
buyuk[node]--;
if (buyuk[node]>0) avab.insert(node);
}
while (kul3.size()){
avab.insert(*kul3.begin());
kul3.erase(kul3.begin());
}
}
allocate_tickets(rval);
return ans;
}
