#include <bits/stdc++.h>
using namespace std;
using ll = long long;
struct Triple {
ll a,b,c;
bool operator==(Triple const& o) const { return a==o.a && b==o.b && c==o.c; }
};
struct TripleHash { size_t operator()(Triple const& t) const noexcept {
// simplu hash combinat
uint64_t x = (uint64_t)t.a * 1000003ULL + (uint64_t)t.b;
x = x * 1000003ULL + (uint64_t)t.c;
return (size_t)(x ^ (x>>32));
}};
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
int N;
if(!(cin>>N)) return 0;
vector<ll> S(9);
for(int i=0;i<9;i++) cin>>S[i];
vector<vector<ll>> a(N, vector<ll>(N));
for(int i=0;i<N;i++){
for(int j=0;j<N;j++){
cin>>a[i][j];
}
}
// precompute column prefix sums: col_pref[r][j] = sum rows 0..r at column j
vector<vector<ll>> col_pref(N, vector<ll>(N,0));
for(int r=0;r<N;r++){
for(int c=0;c<N;c++){
ll above = (r>0 ? col_pref[r-1][c] : 0);
col_pref[r][c] = above + a[r][c];
}
}
// total per column
vector<ll> col_total(N);
for(int c=0;c<N;c++) col_total[c] = col_pref[N-1][c];
// precompute row total prefix (sum of entire rows)
vector<ll> row_sum(N,0), row_pref(N,0);
for(int r=0;r<N;r++){
ll s=0;
for(int c=0;c<N;c++) s += a[r][c];
row_sum[r]=s;
row_pref[r] = (r>0? row_pref[r-1] : 0) + s;
}
// Generate all unordered partitions of indices 0..8 into three groups of 3
// Map key = sorted triple sums -> list of partitions (each partition = vector of three vectors of indices)
struct Part {
array<int,3> g1, g2, g3; // store indices (sorted inside)
ll s1,s2,s3;
};
map<array<ll,3>, vector<Part>> parts_map;
vector<int> idx(9);
iota(idx.begin(), idx.end(), 0);
// combinations for group1
for(int i1=0;i1<9;i1++) for(int i2=i1+1;i2<9;i2++) for(int i3=i2+1;i3<9;i3++){
// group1 = {i1,i2,i3}
vector<int> rem;
for(int t=0;t<9;t++){
if(t==i1 || t==i2 || t==i3) continue;
rem.push_back(t);
}
// choose group2 among rem 6 choose 3
for(int a=0;a<6;a++) for(int b=a+1;b<6;b++) for(int c=b+1;c<6;c++){
array<int,3> g1 = {i1,i2,i3};
array<int,3> g2 = {rem[a], rem[b], rem[c]};
// g3 is leftover
vector<int> used(9,0);
used[i1]=used[i2]=used[i3]=1;
used[rem[a]]=used[rem[b]]=used[rem[c]]=1;
array<int,3> g3;
int p=0;
for(int t=0;t<9;t++) if(!used[t]) g3[p++]=t;
sort(g1.begin(), g1.end());
sort(g2.begin(), g2.end());
sort(g3.begin(), g3.end());
// To avoid duplicates of partitions with same groups in different order,
// ensure lexicographic order of group indices
vector<array<int,3>> gs = {g1,g2,g3};
// sort groups lexicographically to create canonical order for partition
sort(gs.begin(), gs.end(), [](auto const& A, auto const& B){
if(A[0]!=B[0]) return A[0]<B[0];
if(A[1]!=B[1]) return A[1]<B[1];
return A[2]<B[2];
});
// compute sums using S
ll s1 = S[gs[0][0]] + S[gs[0][1]] + S[gs[0][2]];
ll s2 = S[gs[1][0]] + S[gs[1][1]] + S[gs[1][2]];
ll s3 = S[gs[2][0]] + S[gs[2][1]] + S[gs[2][2]];
array<ll,3> key = {s1,s2,s3};
sort(key.begin(), key.end());
Part P;
P.g1 = gs[0]; P.g2 = gs[1]; P.g3 = gs[2];
P.s1 = s1; P.s2 = s2; P.s3 = s3;
parts_map[key].push_back(P);
}
}
// Iterate l1 ascending; for each l1 examine all l2 and keep best candidate for that l1.
bool found_any = false;
int out_l1=0,out_l2=0,out_c1=0,out_c2=0;
for(int l1 = 1; l1 <= N-2; ++l1){
// we will collect best solution for this l1 (according to tie-breakers c1, then l2, then sum)
bool best_for_l1_exist = false;
int best_c1 = INT_MAX, best_l2 = INT_MAX, best_c2 = INT_MAX;
ll best_sum = (1LL<<62);
for(int l2 = l1+1; l2 <= N-1; ++l2){
// compute top_total, mid_total, bot_total
ll top_total = row_pref[l1-1];
ll mid_total = row_pref[l2-1] - row_pref[l1-1];
ll bot_total = row_pref[N-1] - row_pref[l2-1];
array<ll,3> tkey = {top_total, mid_total, bot_total};
array<ll,3> sortedkey = tkey;
sort(sortedkey.begin(), sortedkey.end());
auto it = parts_map.find(sortedkey);
if(it == parts_map.end()) continue; // no partition of S has these three band sums
// Build Ptop, Pmid, Pbot prefix arrays across columns (size N: indices 0..N)
vector<ll> Ptop(N+1,0), Pmid(N+1,0), Pbot(N+1,0);
for(int c=0;c<N;c++){
ll top_col = col_pref[l1-1][c];
ll mid_col = col_pref[l2-1][c] - col_pref[l1-1][c];
ll bot_col = col_total[c] - col_pref[l2-1][c];
Ptop[c+1] = Ptop[c] + top_col;
Pmid[c+1] = Pmid[c] + mid_col;
Pbot[c+1] = Pbot[c] + bot_col;
}
Triple Tot = {Ptop[N], Pmid[N], Pbot[N]}; // should equal (top_total,mid_total,bot_total)
// dict: V(c) -> list of c where V(c) = (Ptop[c],Pmid[c],Pbot[c]), c in [1..N-1]
unordered_map<Triple, vector<int>, TripleHash> mapV;
mapV.reserve(N*2);
for(int c=1;c<=N-1;c++){
Triple tv = {Ptop[c], Pmid[c], Pbot[c]};
mapV[tv].push_back(c); // c ascending insertion => lists sorted
}
// For each partition candidate stored under sortedkey, we must consider the actual partition variants
for(const Part &P : it->second){
// P has groups in canonical order (g1,g2,g3) but these groups are not labeled top/mid/bottom.
// We must consider all 6 permutations mapping these three groups to (top,mid,bottom)
array<array<int,3>,3> groups = {P.g1, P.g2, P.g3};
array<ll,3> sums = {P.s1, P.s2, P.s3};
array<int,3> permIdx = {0,1,2};
for(int perm=0; perm<6; ++perm){
int gi_top = permIdx[0], gi_mid = permIdx[1], gi_bot = permIdx[2];
// Check sums match exact band totals:
ll s_top = sums[gi_top], s_mid = sums[gi_mid], s_bot = sums[gi_bot];
if(!(s_top == top_total && s_mid == mid_total && s_bot == bot_total)){
// rotate permutation
next_permutation(permIdx.begin(), permIdx.end());
continue;
}
// Build arrays of actual numbers for each band (three numbers per band)
ll top_vals[3] = { S[ groups[gi_top][0] ], S[ groups[gi_top][1] ], S[ groups[gi_top][2] ] };
ll mid_vals[3] = { S[ groups[gi_mid][0] ], S[ groups[gi_mid][1] ], S[ groups[gi_mid][2] ] };
ll bot_vals[3] = { S[ groups[gi_bot][0] ], S[ groups[gi_bot][1] ], S[ groups[gi_bot][2] ] };
// For speed, we won't sort top_vals etc; we'll use indices 0..2 and handle duplicates.
// iterate c1 ascending (1..N-2)
for(int c1 = 1; c1 <= N-2; ++c1){
Triple A = {Ptop[c1], Pmid[c1], Pbot[c1]};
// Check if A.a equals one of top_vals and similarly for mid and bot
vector<int> choices_top, choices_mid, choices_bot;
for(int t=0;t<3;t++) if(top_vals[t] == A.a) choices_top.push_back(t);
if(choices_top.empty()) continue;
for(int t=0;t<3;t++) if(mid_vals[t] == A.b) choices_mid.push_back(t);
if(choices_mid.empty()) continue;
for(int t=0;t<3;t++) if(bot_vals[t] == A.c) choices_bot.push_back(t);
if(choices_bot.empty()) continue;
// For every choice of indices used for left segment, build remaining indices per band (2 each)
for(int itopIdx : choices_top){
int remt[2], rp=0;
for(int z=0;z<3;z++) if(z!=itopIdx) remt[rp++]=z;
for(int imidIdx : choices_mid){
int remm[2]; rp=0;
for(int z=0;z<3;z++) if(z!=imidIdx) remm[rp++]=z;
for(int ibotIdx : choices_bot){
int remb[2]; rp=0;
for(int z=0;z<3;z++) if(z!=ibotIdx) remb[rp++]=z;
// Now choose which of remaining become middle for each band (2*2*2 = 8 combos)
for(int rti=0;rti<2;rti++){
ll mid_top_choice = top_vals[ remt[rti] ];
for(int rmi=0;rmi<2;rmi++){
ll mid_mid_choice = mid_vals[ remm[rmi] ];
for(int rbi=0;rbi<2;rbi++){
ll mid_bot_choice = bot_vals[ remb[rbi] ];
// target V(c2) = V(c1) + (mid_top_choice, mid_mid_choice, mid_bot_choice)
Triple target = { A.a + mid_top_choice, A.b + mid_mid_choice, A.c + mid_bot_choice };
auto itv = mapV.find(target);
if(itv == mapV.end()) continue;
// list of possible c2s (sorted), need c2 > c1 (and c2 <= N-1)
const vector<int> &lst = itv->second;
// binary search for first > c1
auto itpos = std::upper_bound(lst.begin(), lst.end(), c1);
if(itpos == lst.end()) continue;
// for tie-breakers we pick minimal c2 > c1; but there may be multiple c2; pick minimal
int cand_c2 = *itpos;
// compute final right segment C = Tot - V(c2)
Triple Vc2 = { Ptop[cand_c2], Pmid[cand_c2], Pbot[cand_c2] };
Triple C = { Tot.a - Vc2.a, Tot.b - Vc2.b, Tot.c - Vc2.c };
// expected right elements (the third elements per band) are the leftovers (the one not used for left and not used for middle)
// find index of the third element per band
int third_top_idx = 0;
for(int z=0;z<3;z++) if(z!=itopIdx && z!=remt[rti]) third_top_idx = z;
int third_mid_idx = 0;
for(int z=0;z<3;z++) if(z!=imidIdx && z!=remm[rmi]) third_mid_idx = z;
int third_bot_idx = 0;
for(int z=0;z<3;z++) if(z!=ibotIdx && z!=remb[rbi]) third_bot_idx = z;
ll expected_right_top = top_vals[third_top_idx];
ll expected_right_mid = mid_vals[third_mid_idx];
ll expected_right_bot = bot_vals[third_bot_idx];
if(C.a == expected_right_top && C.b == expected_right_mid && C.c == expected_right_bot){
// Found valid solution (l1,l2,c1,c2)
// Update best for this l1 according to tie-breaker: minimal c1, then minimal l2, then minimal sum.
ll curr_sum = (ll)l1 + l2 + c1 + cand_c2;
if(!best_for_l1_exist
|| make_tuple(c1, l2, curr_sum) < make_tuple(best_c1, best_l2, best_sum)){
best_for_l1_exist = true;
best_c1 = c1; best_l2 = l2; best_c2 = cand_c2;
best_sum = curr_sum;
}
// Because we want minimal c1 for this l1 overall, we can stop exploring larger c2 for same c1 & same mapping,
// but there may be other combinations leading to even smaller c1 (no, c1 fixed now). We continue to check others.
}
}
}
}
}
}
}
} // end c1 loop
next_permutation(permIdx.begin(), permIdx.end());
} // end permutations
} // end candidate partitions
// After processing this l2, we continue to next l2; we need to explore all l2 to possibly find a smaller c1 for same l1.
} // end l2 loop
if(best_for_l1_exist){
// we found the best solution for the minimal l1; print and exit.
cout<<l1<<" "<<best_l2<<" "<<best_c1<<" "<<best_c2<<"\n";
return 0;
}
} // end l1 loop
return 0;
}
Florea Vlad hackuit vldftz