int n, m;int a, b, x, y;constint dx[4]={
1,1,-1,-1};constint dy[4]={
1,-1,1,-1};intsolve(){
cin >> x >> y;
map<pii,bool> mp;
cin >> a >> b;for(int i =0; i <4; i ++) mp[{
a + dx[i]* x, b + dy[i]* y}]=true;for(int i =0; i <4; i ++) mp[{
a + dx[i]* y, b + dy[i]* x}]=true;int res =0;
cin >> a >> b;for(int i =0; i <4; i ++)if(mp[{
a + dx[i]* x, b + dy[i]* y}]){
res ++;
mp[{
a + dx[i]* x, b + dy[i]* y}]=false;}for(int i =0; i <4; i ++)if(mp[{
a + dx[i]* y, b + dy[i]* x}]){
res ++;
mp[{
a + dx[i]* y, b + dy[i]* x}]=false;}return res;}
int n, m;
pii a[N];
ll pre[N];int ans[N];voidsolve(){
cin >> n;for(int i =1; i <= n; i ++) cin >> a[i].aa, a[i].bb = i;sort(a +1, a + n +1);
ll sum =0;int pos =0;for(int i =1; i <= n; i ++){
if(pos < i) pos ++, sum += a[pos].aa;while(a[pos +1].aa <= sum && pos < n) sum += a[++ pos].aa;
ans[a[i].bb]= pos -1;}for(int i =1; i <= n; i ++) cout << ans[i]<<' ';
cout << endl;}
int n, m;
ll a[N], b[N];
ll solve(){
cin >> n >> m;
ll res =1e18;for(int i =0; i < n; i ++) cin >> a[i], res =min(res, a[i]);if(m >=3)return0;int nn =0;for(int i =0; i < n; i ++){
for(int j = i +1; j < n; j ++){
ll x =abs(a[i]- a[j]);
res =min(res, x);
b[nn ++]= x;}}if(m ==1)return res;sort(b, b + nn);for(int i =0; i < n; i ++){
int l =upper_bound(b, b + nn, a[i])- b -1;int r =lower_bound(b, b + nn, a[i])- b;if(l >=0&& l < nn) res =min(res,abs(a[i]- b[l]));if(r < nn) res =min(res,abs(a[i]- b[r]));}return res;}
int n, m;int a[N], b[N];
string solve(){
cin >> n;for(int i =0; i < n; i ++) cin >> a[i];for(int i =0; i < n; i ++) cin >> b[i];int l =0, r =0;while(r < n){
while(b[r +1]== b[l]&& r +1< n) r ++;int maxx =0;for(int i = l; i <= r; i ++) maxx =max(maxx, a[i]);if(maxx != b[l]){
int L = l, R = r;while(L -1>=0&& a[L -1]<= b[l]&& b[L -1]>= b[l]&& a[L]!= b[l]) L --;while(R +1< n && a[R +1]<= b[l]&& b[R +1]>= b[l]&& a[R]!= b[l]) R ++;if(a[L]!= b[l]&& a[R]!= b[l]|| L == l && R == r)return no;if(L == l && a[R]!= b[l]|| R == r && a[L]!= b[l])return no;}
r ++, l = r;}return yes;}