#include "prison.h"
#include<bits/stdc++.h>
#include <vector>
using namespace std;
const int maxn=5010;
int dp[maxn];
int od[maxn];
int del[maxn];
pair<int,int> rasponx[50];
void napravi(int nivo,int tren,int tx,pair<int,int> ia,pair<int,int> ib,vector<vector<int> > &res){
res[tx][0]=tren;
cout<<ia.first<<" "<<ia.second<<" "<<ib.first<<" "<<ib.second<<endl;
if(tren==0){
for(int i=ia.first;i<=ia.second;i++){
if(i<=ib.first) res[tx][i]=-1;
else if(i>=ib.second) res[tx][i]=-2;
}
if(ib.second-ib.first<2) return;
vector<pair<int,int> > podela;
int klk=rasponx[nivo].second-rasponx[nivo].first+1;
int vel=(ib.second-1-ib.first-1)/klk+1;
int tren=ib.first+1;
while(tren<=ib.second-1){
podela.push_back({tren,min(tren+vel-1,ib.second-1)});
tren+=vel;
}
for(int i=ia.first;i<=ia.second;i++){
if(i<=ib.first) res[tx][i]=-1;
else if(i>=ib.second) res[tx][i]=-2;
else{
for(int j=0;j<(int)podela.size();j++){
if(podela[j].first<=i && i<=podela[j].second){
res[tx][i]=rasponx[nivo].first+j;
break;
}
}
}
}
for(int j=0;j<(int)podela.size();j++){
napravi(nivo+1,1,rasponx[nivo].first+j,{podela[j].first,podela[j].second},ib,res);
}
}else{
for(int i=ib.first;i<=ib.second;i++){
if(i<=ia.first) res[tx][i]=-2;
else if(i>=ia.second) res[tx][i]=-1;
}
if(ia.second-ia.first<2) return;
vector<pair<int,int> > podela;
int klk=rasponx[nivo].second-rasponx[nivo].first+1;
int vel=(ia.second-1-ia.first-1)/klk+1;
int tren=ia.first+1;
while(tren<=ia.second-1){
podela.push_back({tren,min(tren+vel-1,ia.second-1)});
tren+=vel;
}
for(int i=ib.first;i<=ib.second;i++){
if(i<=ia.first) res[tx][i]=-2;
else if(i>=ia.second) res[tx][i]=-1;
else{
for(int j=0;j<(int)podela.size();j++){
if(podela[j].first<=i && i<=podela[j].second){
res[tx][i]=rasponx[nivo].first+j;
break;
}
}
}
}
for(int j=0;j<(int)podela.size();j++){
napravi(nivo+1,0,rasponx[nivo].first+j,ia,{podela[j].first,podela[j].second},res);
}
}
}
vector<vector<int> > devise_strategy(int n) {
dp[0]=dp[1]=dp[2]=0;
for(int i=3;i<maxn;i++){
dp[i]=maxn;
for(int j=1;j<=i-2;j++){
dp[i]=min(dp[i],j+dp[(i-3)/j+1]);
if(dp[i]==j+dp[(i-3)/j+1]){
od[i]=(i-3)/j+1;
del[i]=j;
}
}
}
int tren=n;
vector<int> klk;
while(dp[tren]>0){
klk.push_back(del[tren]);
tren=od[tren];
}
int sum=1;
for(int i=0;i<(int)klk.size();i++){
rasponx[i]={sum,sum+klk[i]-1};
sum+=klk[i];
}
vector<vector<int> > res(dp[n]+1,vector<int>(n+1));
napravi(0,0,0,{1,n},{1,n},res);
return res;
}
