前几天机房里打了 BOI2025 的 VP 赛，VP Day1 的时候在这题卡了很久，以为难度是顺序的，于是就硬开这题，还真开出来了。但是没时间过 T2 了，幸好其他人也没过 T2。

看了眼题解区，感觉都太人类智慧了。那我们来一篇乱搞题解，充分发扬类人思维。

思路

先尝试发掘一点性质，发现输入信息等价于让是你知道任意区间的众数的出现次数。想一想我们有什么可以干的事。

显然，我们可以把一个字符相同的极大区间给缩起来，考虑从右往左做，每次判定 $cnt_{l,r} +1 =cnt_{l-1,r}$。若成功，则说明 $l-1$ 这个位置的数和 $l$ 位置上的数一样，都是 $[l,r]$ 的众数。

那么问题转化成要给 $M$ 个连续段分配 B、O、I 三个字符，同时要求最后填出来的字符串符合 $cnt_{l,r}$ 的约束。

想到这里就想不下去了，拼尽全力找不出其它有用的东西，那么就从这里开始做吧。

直接做是什么样的？$O(3^B)$ 暴力枚举每个点放什么字符。最后 $O(n^2)$ 算新的 $cnt'_{l,r}$ 数组来判断是否方案合法。

首先发现由于我们已经划了极大相同字符子段，所以相邻的字符一定不同，于是复杂度降为 $O(n^2\times 2^B)$。

似乎这里已经能过 44pts 了，但是我钦定大家认为这题是签到题，必须过掉。

考虑一个比较关键的事情，就是我们能不能减少一点无效的状态转移。进行长达 1h 的发呆式思考发现：设相邻的三个连续段长度分别为 $x$、$y$、$z$，若 $x+z>y$ 那么我们可以直接查询这三段合起来的大段的 $cnt$ 是多少，如果是 $x+z$ 那么说明 $ch_x=ch_y$，否则两者不同，这个很显然是对的。

那么我们通过判定这玩意可以将复杂度降为 $O(n^2\times 2^{B/2})$，因为如果说某个 $x+z \le y$ 那么必定会有 $w+y > x$，这个 $w$ 是 $x$ 的前一段，所以相当于只会有一半的点拥有两个后继状态。但是这玩意加上去似乎也没啥吊用。

马上就要去吃饭了，你必须快点想出做法。

你发现它在比较大的子任务中依然跑得飞快，于是你认为这个东西再剪一剪枝就能卡过，事实上你赛后把它交到了洛谷上发现确实仅 TLE 了四个点。

来不及了，可是我们还没战胜那四个点！但是这四个数据数据估计还是很水，考虑乱剪一通。

你发现合法性的判定其实很慢，而且由于你前面已经缩过了连续段，判过了可以直接推的情况，那么剩下需要你判的东西应该不会很多。于是你断言只需要判横跨当前决策的段和它前面的段的区间就可以了，但是你发现这依然有个 $O(n^2)$ 的判定复杂度，好像还是很慢。

于是你充分发扬类人智慧，盲猜在上述判定的所有区间中，只需要判左端点为目前填了的最靠左的点的那些区间众数即可。因为感性理解起来确实区间越大，越有可能判出问题，但是仔细想想，似乎并没有什么道理。

同时为了保证复杂度为 $O(n\times ? )$，你舍弃了最后找到方案时的完整判定，因此这个做法正确性也存疑。

做法

类人智慧，暴搜乱搞。

时间复杂度：$O(n\times 2^C)$，其中 $C$ 是一个小于 $B$ 的东西且我也不知道它会有多大。

代码

#include<bits/stdc++.h>
#define PII pair<int,int>
#define DB double
#define LL long long
#define comp complex<double>
#define int long long
//#define int __int128
//const int mod=1e9+7;
//const int mod=998244353;
const LL inf=0x3f3f3f3f,INF=0x3f3f3f3f3f3f3f3f,Inf=0x66ccff66ccff;
const DB pi=acos(-1);
namespace FastIO{
	inline int read(int mod=0){
		int x=0,f=1;char ch=getchar();
		if(mod==0){while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=x*10+ch-48;ch=getchar();}}
		else{while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=(x*10%mod+ch-48)%mod;ch=getchar();}}
		return x*f;}
	#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)
	char buf[1<<23],*p1=buf,*p2=buf,obuf[1<<23],*O=obuf;
	inline int rd(){
		int x=0,f=1;char ch=getchar();
		while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=x*10+ch-48;ch=getchar();}
		return x*f;
	}//8(:D
}
using namespace FastIO;
using namespace std;
bool mp[1005];
char str[2005];
int cnt[2005][2005],sum[1005][2005],n;
vector<PII>vec;
vector<char>ch;
vector<int>ans;
void dfs(int x){
	for(int i=vec[x-1].second+1;i<=n;++i){
		int sumB=sum['B'][vec[x-1].first]-sum['B'][i+1],sumI=sum['I'][vec[x-1].first]-sum['I'][i+1],sumO=sum['O'][vec[x-1].first]-sum['O'][i+1];
		if(cnt[vec[x-1].first][i]!=max({sumB,sumI,sumO}))return;
	}
	if(x==(int)vec.size()){
		for(int i=0;i<(int)vec.size();++i){
			int l=vec[i].first,r=vec[i].second;
			for(int j=l;j<=r;++j)str[j]=ch[i];
			if(ch[i]!='B')continue;
			for(int j=l;j<=r;++j)ans.push_back(j);
		}sort(ans.begin(),ans.end());
		for(int pos:ans)printf("%lld ",pos);
		exit(0);
	}
	int l=vec[x].first,r=vec[x-2].second,cnt0=vec[x].second-vec[x].first+1,cnt1=vec[x-1].second-vec[x-1].first+1,cnt2=vec[x-2].second-vec[x-2].first+1;
	if(cnt0+cnt2>cnt1&&cnt[l][r]==max({cnt0,cnt1,cnt2})){
		mp[ch[x-1]]=1,mp[ch[x-2]]=1;
		if(!mp['B'])ch.push_back('B');
		if(!mp['I'])ch.push_back('I');
		if(!mp['O'])ch.push_back('O');
		mp[ch[x-1]]=0,mp[ch[x-2]]=0;
		for(int i=vec[x].second;i>=vec[x].first;--i){
			sum['B'][i]=sum['B'][i+1],sum['I'][i]=sum['I'][i+1],sum['O'][i]=sum['O'][i+1];
			++sum[ch[x]][i];
		}dfs(x+1),ch.pop_back();
	}
	else if(cnt0+cnt2>cnt1){
		ch.push_back(ch[x-2]);
		for(int i=vec[x].second;i>=vec[x].first;--i){
			sum['B'][i]=sum['B'][i+1],sum['I'][i]=sum['I'][i+1],sum['O'][i]=sum['O'][i+1];
			++sum[ch[x]][i];
		}dfs(x+1),ch.pop_back();
	}
	else{
		ch.push_back(ch[x-2]);
		for(int i=vec[x].second;i>=vec[x].first;--i){
			sum['B'][i]=sum['B'][i+1],sum['I'][i]=sum['I'][i+1],sum['O'][i]=sum['O'][i+1];
			++sum[ch[x]][i];
		}dfs(x+1),ch.pop_back();
		mp[ch[x-1]]=1,mp[ch[x-2]]=1;
		if(!mp['B'])ch.push_back('B');
		if(!mp['I'])ch.push_back('I');
		if(!mp['O'])ch.push_back('O');
		mp[ch[x-1]]=0,mp[ch[x-2]]=0;
		for(int i=vec[x].second;i>=vec[x].first;--i){
			sum['B'][i]=sum['B'][i+1],sum['I'][i]=sum['I'][i+1],sum['O'][i]=sum['O'][i+1];
			++sum[ch[x]][i];
		}dfs(x+1),ch.pop_back();
	}
}
signed main(){
	n=read(0);
	for(int i=1;i<=n;++i)
		for(int j=i;j<=n;++j)
			cnt[i][j]=read(0);
	for(int i=n,j=i;i>=1;i=j-1){
		while(j>1&&cnt[j-1][i]==i-j+2)--j;
		vec.push_back({j,i});
	}
	if(vec.size()==1)for(int i=1;i<=n;++i)printf("%lld ",i);
	else{
		if(cnt[1][n]==cnt[1][n-1]){
			int l=vec[1].first;ch.push_back('I');
			if(cnt[1][l-1]==cnt[1][n])ch.push_back('O');
			else ch.push_back('B');
		}else ch.push_back('B'),ch.push_back('I');
		for(int i=vec[0].second;i>=vec[0].first;--i){
			sum['B'][i]=sum['B'][i+1],sum['I'][i]=sum['I'][i+1],sum['O'][i]=sum['O'][i+1];
			++sum[ch[0]][i];
		}
		for(int i=vec[1].second;i>=vec[1].first;--i){
			sum['B'][i]=sum['B'][i+1],sum['I'][i]=sum['I'][i+1],sum['O'][i]=sum['O'][i+1];
			++sum[ch[1]][i];
		}dfs(2);	
	}
	return 0;
}