#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> P;
typedef tuple<ll,ll,ll> PP;
typedef vector<ll> vi;
typedef vector<vi> vvi;
typedef vector<P> vp;
typedef vector<bool> vb;
typedef vector<vb> vvb;
#define rep(i,n) for(ll i=0;i<(ll)(n);i++)
#define REP(i,k,n) for(ll i=(ll)(k);i<(ll)(n);i++)
#define pb emplace_back
#define fi first
#define se second
template<class T> void out(T a){cout<<a<<endl;}
template<class T> bool chmin(T&a,T b){if(a>b){a=b;return true;}return false;}
template<class T> void outv(T v){rep(i,v.size()){if(i)cout<<' ';cout<<v[i];}cout<<endl;}
const ll inf=1001001001001001001;
struct segtree{
vp seg;vi lazy;
ll n=1;
segtree(vp v){
while(n<v.size())n*=2;
seg=vp(n*2,P(2*inf,0));lazy=vi(n*2);
rep(i,v.size())seg[i+n]=v[i];
for(ll i=n-1;i>0;i--)seg[i]=min(seg[i*2],seg[i*2+1]);
}
void eval(ll k,ll l,ll r){
seg[k].fi+=lazy[k];
if(r-l>1)rep(j,2)lazy[k*2+j]+=lazy[k];
lazy[k]=0;
}
P get(ll a,ll b,ll k=1,ll l=0,ll r=-1){
if(r==-1)r=n;
eval(k,l,r);
if(r<=a||b<=l)return P(2*inf,0);
if(a<=l&&r<=b)return seg[k];
return min(get(a,b,k*2,l,(l+r)/2),get(a,b,k*2+1,(l+r)/2,r));
}
void add(ll x,ll a,ll b,ll k=1,ll l=0,ll r=-1){
if(r==-1)r=n;
eval(k,l,r);
if(r<=a||b<=l)return;
if(a<=l&&r<=b){
lazy[k]+=x;eval(k,l,r);return;
}
add(x,a,b,k*2,l,(l+r)/2);
add(x,a,b,k*2+1,(l+r)/2,r);
seg[k]=min(seg[k*2],seg[k*2+1]);
}
};
vi num,al,rv;
vvi ma,mi;
ll k,n;
vvb ans;
void init(int K_,vector<int> v){
k=K_;n=v.size();
vp tmp1(n),tmp2(n);
rep(i,n)tmp1[i]=P(v[i],i);
rep(i,n)tmp2[i]=P(inf,i);
segtree seg1(tmp1),seg2(tmp2);
auto dif=[&](ll x){
return (x%n+n)%n;
};
ll cnt=0;
num=vi(n);
while(true){
while(true){
auto tmp=seg1.get(0,n);
if(tmp.fi>0)break;
ll i=tmp.se;
seg1.add(inf,i,i+1);
seg2.add(-inf,i,i+1);
if(i+k<=n)seg2.add(1,i+1,i+k);
else{
seg2.add(1,i+1,n);
seg2.add(1,0,i+k-n);
}
}
auto tmp=seg2.get(0,n);
if(tmp.fi>0)break;
ll i=tmp.se;
seg2.add(inf,i,i+1);
num[i]=cnt++;
if(i-k+1>=0)seg1.add(-1,i-k+1,i);
else{
seg1.add(-1,0,i);
seg1.add(-1,i-k+1+n,n);
}
if(i+k<=n)seg2.add(-1,i+1,i+k);
else{
seg2.add(-1,i+1,n);
seg2.add(-1,0,i+k-n);
}
}
al=vi(n*3);
rep(i,n)al[num[i]*3]=i;
rep(i,n)al[num[i]*3+1]=i+n;
rep(i,n)al[num[i]*3+2]=i+n*2;
rv=vi(n*3);rep(i,n*3)rv[al[i]]=i;
vvi g(n*3);
rep(i,n*3)rep(j,k-1){
ll t=i+j+1;
if(t>=n*3)continue;
if(rv[i]<rv[t])g[i].pb(t);
else g[t].pb(i);
}
vvb tmp(n*3,vb(n*3,false));
rep(i,n*3){
queue<ll> que;
que.push(i);tmp[i][i]=true;
while(!que.empty()){
ll t=que.front();que.pop();
for(ll x:g[t])if(!tmp[i][x]){
tmp[i][x]=true;que.push(x);
}
}
}
ans=vvb(n,vb(n,false));
rep(i,n)rep(j,n)if(tmp[i+n][j]||tmp[i+n][j+n]||tmp[i+n][j+n*2])ans[i][j]=true;
}
int compare_plants(int x,int y){
int f=-1;
if(num[x]<num[y]){
swap(x,y);
f=1;
}
ll j=rv[x+n],i=rv[y+n];
{
ll cur=i;
REP(t,i+1,j+1)if(al[t]-al[cur]<k&&al[t]>al[cur])cur=t;
ll tmp=x+n;
if(x<y)tmp+=n;
if(al[cur]>=tmp)return f;
}
{
ll cur=i;
REP(t,i+1,j+1)if(al[cur]-al[t]<k&&al[cur]>al[t])cur=t;
ll tmp=x+n;
if(x>y)tmp-=n;
if(al[cur]<=tmp)return f;
}
return 0;
}
