stablegradients/pie-gem5-bysrc huggingface dataset:
// Original C++ solution (slower):
#include <cstdio>

#include <iostream>

#include <algorithm>

#include <cstdlib>

#define Pi 3.1415926535898

//#define mp{(x),(y)} make_pair{(x),(y)}

#define _1 first

#define _2 second

#define LL long long

#define maxn 200000+10

const int INF = 1e9+7;

using namespace std;



int k,flag=1,x1,x2,y1,x,y,y2,n,cnt;

int st[maxn];

double ans;

pair <int ,int > a[maxn];



int cmp(pair<int ,int > A,pair<int ,int > B)

{

	return A._1<B._1;

}



int main()

{

	scanf("%d%d%d%d",&x1,&y1,&x2,&y2);

	if (x1>x2) swap(x1,x2),swap(y1,y2);

	if (y1>y2) flag=-1;

	y1*=flag;y2*=flag;

	scanf("%d",&n);

	for (int i=1;i<=n;++i)

	  {

	  	scanf("%d%d",&x,&y);y*=flag;

	  	if (x<x1||x>x2||y<y1||y>y2) continue;

	  	a[++cnt]={x,y};

	  }

	sort(a+1,a+1+cnt,cmp)	;

	st[0]=-INF;for (int i=1;i<=n+2;++i) st[i]=INF;

	for (int i=1;i<=cnt;++i)

	{

		int y=a[i]._2;

		int pos=upper_bound(st,st+n+2,y)-st;

		st[pos]=y;

	}

	k=lower_bound(st,st+n+2,INF)-st-1;

	//cnt-1;

	//cout.precision(25);

	int len=min(x2-x1,y2-y1);

	ans=(LL)(x2-x1+y2-y1)*(LL)100;

	ans-=20*k;

	ans+=5*k*Pi;

	if (len+1==k) ans+=5*Pi;;

	printf("%.15f\n",ans);

	return 0;

}

// Optimized solution to the same problem (faster):
#include <cstdio>

#include <algorithm>

#define Pi 3.1415926535898

#define _1 first

#define _2 second

#define LL long long

#define maxn 200010

#define P pair <int ,int>

const int INF = 1e9+7;

using namespace std;

int k,flag=1,x1,pos,x2,y1,x,y,y2,n,cnt,st[maxn];

double ans;

P a[maxn];

int cmp(P A,P B){return A._1<B._1;}

int main()

{

	scanf("%d%d%d%d%d",&x1,&y1,&x2,&y2,&n);

	if (x1>x2) swap(x1,x2),swap(y1,y2);

	if (y1>y2) flag=-1,y1*=flag,y2*=flag;

	for (int i=1;i<=n;++i)

	  {

	  	scanf("%d%d",&x,&y);y*=flag;

	  	if (!(x<x1||x>x2||y<y1||y>y2)) a[++cnt]={x,y};

	  }

	sort(a+1,a+1+cnt,cmp);

	st[0]=-INF;for (int i=1;i<=n+2;++i) st[i]=INF;

	for (int i=1;i<=cnt;++i)

	{

		y=a[i]._2;

		pos=upper_bound(st,st+n+2,y)-st;

		st[pos]=y;

	}

	k=lower_bound(st,st+n+2,INF)-st-1;

	printf("%.15f\n",(LL)(x2-x1+y2-y1)*(LL)100-20*k+5*k*Pi+(min(x2-x1,y2-y1)+1==k?5*Pi:0));

	return 0;

}

// Fastest known solution for this problem:
// Original C++ solution (slower):
#include <iostream>

#include <stdio.h>

#include <string>

using namespace std;



int main()

{



    char s[100] ;

    cin >> s ;

    int i , j , x , rs = 1;

    for (i = 0 ; i <100 ; i++){

        if (s[i] == '\0')

            break;

    }



    x= i;

    for (i=0 , j=x-1  ; i<x && j>0  ; i++ , j--){

        if(s[i] != s[j])

            rs++;

    }





    cout << rs/2 << endl ;



}


// Optimized solution to the same problem (faster):
#include<stdio.h>

int main()

{

    char s[200];



    scanf("%s",s);



    int len=0;



    for(int i=0; s[i]!=0;i++)

    len++;



    int count=0;

    for(int i=0,j=(len-1);i<=j;i++,j--)

    {

        if(s[i]!=s[j])

        count++;

    }



    printf("%d",count);

    return 0;

}


// Fastest known solution for this problem:
// Original C++ solution (slower):
#include<bits/stdc++.h>

using namespace std;



int main(){

    string s;

    cin>>s;

    int count = 0;

    int n = s.size();

    for (int i = 0; i < n/2; i++){

        if (s[i] != s[n-i-1]) count++;

    }

    cout<<count;

}


// Optimized solution to the same problem (faster):
#include<stdio.h>

int main()

{

    char s[200];



    scanf("%s",s);



    int len=0;



    for(int i=0; s[i]!=0;i++)

    len++;



    int count=0;

    for(int i=0,j=(len-1);i<=j;i++,j--)

    {

        if(s[i]!=s[j])

        count++;

    }



    printf("%d",count);

    return 0;

}


// Fastest known solution for this problem:
// Original C++ solution (slower):
#include<cstring>

#include<cstdio>

#include<iostream>

using namespace std;

int main() {

	string s;

	cin >> s;

	int ans=0;

	for(int i=0;i<s.size()/2;i++) {

		if(s[i]!=s[s.size()-i-1]) ans++;

	}

	cout << ans << endl;

} 

// Optimized solution to the same problem (faster):
#include<stdio.h>

int main()

{

    char s[101];



    scanf("%s",s);



    int len=0;



    for(int i=0; s[i]!=0;i++)

    len++;



    int count=0;

    for(int i=0,j=(len-1);i<=j;i++,j--)

    {

        if(s[i]!=s[j])

        count++;

    }



    printf("%d",count);

    return 0;

}


// Fastest known solution for this problem:
// Original C++ solution (slower):
#include <iostream>

#include <string>

#include <cmath>



using namespace std;





int main()

{

    ios::sync_with_stdio(0);

  string s;

    cin>>s;

    int n=s.length(),c=0;

    for(int i=0;i<n/2;i++)

    {

        if(s[i]!=s[n-i-1])

           c++;

    }

    cout<<c;

}


// Optimized solution to the same problem (faster):
#include<stdio.h>

int main()

{

    char s[101];



    scanf("%s",s);



    int len=0;



    for(int i=0; s[i]!=0;i++)

    len++;



    int count=0;

    for(int i=0,j=(len-1);i<=j;i++,j--)

    {

        if(s[i]!=s[j])

        count++;

    }



    printf("%d",count);

    return 0;

}


// Fastest known solution for this problem:
// Original C++ solution (slower):
#include<bits/stdc++.h>



using namespace std;

int main()

{

 string s;

 cin>>s;

 int n=s.size();

 int i,ans=0;

 for(i=0;i<n;i++)

 {

  if(s[i]!=s[n-i-1]) ans++;

  }

  cout<<ans/2;



 }
























// Optimized solution to the same problem (faster):
#include<stdio.h>

int main()

{

    char s[101];



    scanf("%s",s);



    int len=0;



    for(int i=0; s[i]!=0;i++)

    len++;



    int count=0;

    for(int i=0,j=(len-1);i<=j;i++,j--)

    {

        if(s[i]!=s[j])

        count++;

    }



    printf("%d",count);

    return 0;

}


// Fastest known solution for this problem:
// Original C++ solution (slower):
#include<bits/stdc++.h>

int  main()

{

    char s[200];

    scanf("%s", s);



    int len = 0;

    for(int i=0;s[i] !=0 ; i++)

    len++;

    int cnt =0;

    for(int i=0,j=len-1; i<=j ;i++,j--)

    if(s[i] != s[j])

    {

       cnt++;

    }

    printf("%d",cnt);



    return 0;

}


// Optimized solution to the same problem (faster):
#include<stdio.h>

int main()

{

    char s[101];



    scanf("%s",s);



    int len=0;



    for(int i=0; s[i]!=0;i++)

    len++;



    int count=0;

    for(int i=0,j=(len-1);i<=j;i++,j--)

    {

        if(s[i]!=s[j])

        count++;

    }



    printf("%d",count);

    return 0;

}


// Fastest known solution for this problem:
// Original C++ solution (slower):
#include<bits/stdc++.h>

using namespace std;

const int N = 1e5 + 10;

int n , cs[N] , k;

string s;

int freq[N];

int main(){

    cin >> n >> k ;

    cin >> s;

    memset(freq , -1 , sizeof freq);

    cs[0] = (s[0] == '0');

    freq[0] += (s[0] == '1');

    int ans = 1;

    for(int i = 1 ; i < s.size() ; i++){

        if(s[i] == s[i - 1] || s[i] == '1')

            cs[i] = cs[i - 1];

        else

            cs[i] = cs[i - 1] + 1;

        if(cs[i] <= k){

            ans = i + 1;

        }else{

        if(freq[cs[i] - k] != -1)

        ans = max(ans , i - freq[cs[i] - k] + 1);}

        if(s[i] == '1' && freq[cs[i]] == -1) freq[cs[i]] = i;  

    }

    cout << ans << endl;

    return 0;

}

// Optimized solution to the same problem (faster):
#include<bits/stdc++.h>

using namespace std;

const int N = 2e5 + 10;

int n , k;

string s , t;

int main(){

    cin >> n >> k;

    cin >> s;

    int i = 0 , j = 1 , ans = 1 , cost = 0;

    cost += (s[0] == '0');

    while(j < n){

        if(s[j] == '0' && s[j] != s[j - 1])

            cost++;

        while(cost > k){

            if(s[i] == '0'){

               cost--;

               while(s[i] == '0')i++;

               break;

            }

            i++;

        }

        ans = max(ans , j - i + 1);

        j++;

    }

    cout << ans << endl;

    return 0;

}

// Fastest known solution for this problem:
// Original C++ solution (slower):
#include <bits/stdc++.h>



using namespace std;



const int N = 1e5 + 10;



int n, m;

char s[N], t[N];

map<long long, char> Map;



int main()

{

	scanf("%d%d", &n, &m);

	scanf("%s", s + 1);

	scanf("%s", t + 1);

	if(s[1] != t[1])

	{

		puts("-1");

		return 0;

	}

	if(n % m == 0)

	{

		int flag = 1;

		for(int i = 1; i <= m; i++)

			if(t[i] != s[1ll * (i - 1) * n / m + 1])flag = 0;

		if(!flag)

		{

			puts("-1");

		}

		else printf("%d\n", n);

		return 0;

	}

	if(m % n == 0)

	{

		int flag = 1;

		for(int i = 1; i <= n; i++)

			if(s[i] != t[1ll * (i - 1) * m / n + 1])flag = 0;

		if(!flag) 	

		{

			puts("-1");

		}

		else printf("%d\n", m);

		return 0;

	}

	long long nowans = 1ll * n * m / __gcd(n, m);

	for(int i = 1; i <= n; i++)

		Map[1ll * (i - 1) * (nowans / n) + 1] = s[i];

	for(int i = 1; i <= m; i++)

	{

		long long nowx = 1ll * (i - 1) * (nowans / m) + 1;

		if(Map.find(nowx) != Map.end())

		{

			if(t[i] != Map[nowx])

			{

				puts("-1");

				return 0;

			}

		}

	}

	printf("%lld\n", nowans);

}

// Optimized solution to the same problem (faster):
#include <cstdio>

#include <cmath>



#define maxn 100010

char s[maxn], t[maxn];

int gcd(int a, int b)

{

	return !b ? a : gcd(b, a % b);

}

typedef long long ll;

int main()

{

	int n, m; scanf("%d%d", &n, &m);

	scanf("%s%s", s, t);

	bool flag = 1;

	ll ans = 1ll * n * m / gcd(n, m);

	for (int i = 0; i < n; ++i)

		if (i * (ans / n) % (ans / m) == 0)

			flag &= s[i] == t[i * (ans / n) / (ans / m)];

	if (flag)

		printf("%lld\n", ans);

	else puts("-1");

	return 0;

}

/*

6 3

abbcca

abc

*/

// Fastest known solution for this problem:
// Original C++ solution (slower):
#include <cstdio>

#include <bits/stdc++.h>



using namespace std;



int main() {

  int N, M;

  scanf("%d%d", &N, &M);

  char S[100000], T[100000];

  scanf("%s%s", S, T);

  

  // 最大公約数を計算

  int g = __gcd(N, M);

  int stepS = N / g;

  int stepT = M / g;

  for (int i = 0; i < g; ++i) {

    if (S[stepS * i] != T[stepT * i]) {

      cout << -1 << '\n';

      return 0;

    }

  }

  cout << (long long) N / g * M << '\n';

  return 0;

}


// Optimized solution to the same problem (faster):
#include<cstdio>

#include<algorithm>

using namespace std;

int n, m;

char p[101000], q[101000];

int gcd(int a, int b) {

	return b ? gcd(b, a%b) : a;

}

int main() {

	int i;

	scanf("%d%d", &n, &m);

	scanf("%s%s", p, q);

	int g = gcd(n, m);

	for (i = 0; i < n; i++) {

		if (i % (n / g) == 0) {

			if (p[i] != q[i / (n / g) * (m / g)]) {

				puts("-1");

				return 0;

			}

		}

	}

	printf("%lld\n", 1ll * n*m / g);

}


// Fastest known solution for this problem:
// Original C++ solution (slower):
#include <cstdio>

#include <bits/stdc++.h>



using namespace std;



int N, M;

char S[100000], T[100000];



int main() {

  int i;

  scanf("%d%d", &N, &M);

  scanf("%s%s", S, T);

  

  // 最大公約数を計算

  int g = __gcd(N, M);

  int stepS = N / g;

  int stepT = M / g;

  for (i = 0; i < g; ++i) {

    if (S[stepS * i] != T[stepT * i]) {

      puts("-1");

      return 0;

    }

  }

  printf("%lld", 1ll * N / g * M);

  return 0;

}

// Optimized solution to the same problem (faster):
#include<cstdio>

#include<algorithm>

using namespace std;

int n, m;

char p[101000], q[101000];

int gcd(int a, int b) {

	return b ? gcd(b, a%b) : a;

}

int main() {

	int i;

	scanf("%d%d", &n, &m);

	scanf("%s%s", p, q);

	int g = gcd(n, m);

	for (i = 0; i < n; i++) {

		if (i % (n / g) == 0) {

			if (p[i] != q[i / (n / g) * (m / g)]) {

				puts("-1");

				return 0;

			}

		}

	}

	printf("%lld\n", 1ll * n*m / g);

}


// Fastest known solution for this problem:
// Original C++ solution (slower):
#include <bits/stdc++.h>



#define fr first

#define sc second

#define pb push_back

#define mk make_pair

#define ll long long

#define OK puts("OK")

#define sz(s) (int)s.size()

#define all(s) s.begin(), s.end()



using namespace std;



const int N = 2e5+10;

const int inf = 1e9+7;



int n;

int a[N];

int ans[N];

pair <int, int> p[N];



int main() {

    cin >> n;

    for(int i = 1; i <= n; i++) {

        cin >> p[i].fr;

        p[i].sc = i;



    }

    sort(p + 1, p + n + 1);

    for(int i = 1; i <= n; i++) {

        if(i > n / 2)

            ans[p[i].sc] = p[n / 2].fr;

        else

            ans[p[i].sc] = p[n / 2 + 1].fr;

    }

    for(int i = 1; i <= n; i++)

        cout << ans[i] << endl;

}


// Optimized solution to the same problem (faster):
#include <stdio.h>

#include <algorithm>

int a[200005];

int b[200005];

int main(){

    int n,v,mid;

    scanf("%d",&n);

    for(int i=0;i<n;i++){

        scanf("%d",&v);

        a[i]=v;

        b[i]=v;

    }

    std::sort(b,b+n);

    mid = b[n/2-1];

    for(int i=0;i<n;i++){

        if(a[i]>mid){

          printf("%d\n",mid);

        }else{

            printf("%d\n",b[n/2]);

        }



    }

}


// Fastest known solution for this problem:
// Original C++ solution (slower):
#include <bits/stdc++.h>



#define fr first

#define sc second



using namespace std;



const int N = 3e5 + 7;



int a[N];

pair<int, int> b[N];

int c[N];



main()

{

    int n, r, l;



    cin >> n;



    for (int i = 1; i <= n; i++)

    {

        scanf("%d", &a[i]);

        b[i].fr = a[i];

        b[i].sc = i;

    }



    sort(b + 1, b + n + 1);



    for (int i = 1; i <= n; i++)

    {

        c[b[i].sc] = i;

    }



    l = n / 2;

    r = n / 2 + 1;



    for (int i = 1; i <= n; i++)

    {

        int ans;

        if (c[i] <= l)

        {

            ans = b[r].fr;

        }

        else

        {

            ans = b[l].fr;

        }

        printf("%d\n", ans);

    }

}






// Optimized solution to the same problem (faster):
#include <stdio.h>

#include <algorithm>

int a[200005];

int b[200005];

int main(){

    int n,v,mid;

    scanf("%d",&n);

    for(int i=0;i<n;i++){

        scanf("%d",&v);

        a[i]=v;

        b[i]=v;

    }

    std::sort(b,b+n);

    mid = b[n/2-1];

    for(int i=0;i<n;i++){

        if(a[i]>mid){

          printf("%d\n",mid);

        }else{

            printf("%d\n",b[n/2]);

        }



    }

}


// Fastest known solution for this problem:
// Original C++ solution (slower):
#include <bits/stdc++.h>



using namespace std;



const int N = 234567;



int n, a, p[N], r;

vector<pair<int, int> > b;



int main() {



  cin >> n;

  for (int i = 0; i < n; ++i) { cin >> a; b.push_back(make_pair(a, i)); }



  sort(b.begin(), b.end());

  for (int i = 0; i < n; ++i) {

    p[b[i].second] = i;

  }



  for (int i = 0; i < n; ++i) {

    if (p[i] <= n / 2 - 1) { r = b[n / 2].first; }

    else { r = b[n / 2 - 1].first; }  

    cout << r << endl;

  }

  

  return 0;

}

// Optimized solution to the same problem (faster):
#include <stdio.h>

#include <algorithm>

int a[200005];

int b[200005];

int main(){

    int n,v,mid;

    scanf("%d",&n);

    for(int i=0;i<n;i++){

        scanf("%d",&v);

        a[i]=v;

        b[i]=v;

    }

    std::sort(b,b+n);

    mid = b[n/2-1];

    for(int i=0;i<n;i++){

        if(a[i]>mid){

          printf("%d\n",mid);

        }else{

            printf("%d\n",b[n/2]);

        }



    }

}


// Fastest known solution for this problem:
// Original C++ solution (slower):
#include <bits/stdc++.h>

using namespace std;



#define int long long



const int N = 2e5 + 10;

int n;



struct TMP {

	int x, indx, ans;

	

	TMP() {

		x = indx = ans = 0;

	}

} ar[N];



int32_t main() {

	ios::sync_with_stdio(0);

	cin.tie(0);

	

	cin >> n;

	for (int i = 0; i < n; i++)

		cin >> ar[i].x, ar[i].indx = i;

	sort(ar, ar + n, [&] (TMP a, TMP b) { return a.x < b.x; });

	

	for (int i = 0; i < n; i++)

		if (i < n / 2)

			ar[i].ans = ar[n / 2].x;

		else

			ar[i].ans = ar[n / 2 - 1].x;

	sort(ar, ar + n, [&] (TMP a, TMP b) { return a.indx < b.indx; });

	

	for (int i = 0; i < n; i++)

		cout << ar[i].ans << '\n';

}

// Optimized solution to the same problem (faster):
#include <bits/stdc++.h>



using namespace std;



#define int long long



const int N = 2e5 + 100;



int a[N], b[N];

int n, ind;



int32_t main() {

    ios_base::sync_with_stdio(false), cin.tie(0), cout.tie(0);

    cin >> n;

    for (int i = 0; i < n; i++) {

	cin >> a[i];

	b[i] = a[i];

    }

    sort(b, b + n);

    ind = n / 2 - 1;

    for (int i = 0; i < n; i++)

	cout << (a[i] <= b[ind] ? b[ind + 1] : b[ind]) << '\n';

}

// Fastest known solution for this problem:
// Original C++ solution (slower):
#include <iostream>

#include <cstdio>

#include <cstdlib>

#include <iomanip>



#include <vector>

#include <cstring>

#include <string>

#include <queue>

#include <deque>

#include <stack>

#include <map>

#include <set>

#include <unordered_map>

#include <unordered_set>

#include <utility>

#include <list>



#include <cmath>

#include <algorithm>

#include <cassert>

#include <bitset>

#include <complex>



using namespace std;



typedef long long ll;

typedef pair<int, int> ii;

typedef pair<ll, ll> l4;



#define mp make_pair

#define pb push_back



const int maxn = 2e5+1;

int n, a[maxn], sorted[maxn];



int main()

{

  scanf("%d", &n);

  for (int i = 1; i <= n; ++i)

    scanf("%d", a+i);

  memcpy(sorted, a, sizeof(sorted));

  sort(sorted+1, sorted+1+n);

  for (int i = 1; i <= n; ++i)

    printf("%d\n", a[i]<=sorted[n/2]?sorted[n/2+1]:sorted[n/2]);

}


// Optimized solution to the same problem (faster):
#include <bits/stdc++.h>

using namespace std;

typedef long long lli;



int n,a[200000],b[200000];

int main() {

	scanf("%d",&n);

	for(int i=0;i<n;i++)

		scanf("%d",a+i),b[i]=a[i];



	sort(b,b+n);

	for(int i=0;i<n;i++) {

		if(a[i]<=b[n/2-1]) printf("%d\n",b[n/2]);

		else printf("%d\n",b[n/2-1]);

	}



	return 0;

}

// Fastest known solution for this problem:
// Original C++ solution (slower):
#include "bits/stdc++.h"

using namespace std;

typedef long long ll;

typedef pair<int, int> pii;

typedef pair<ll, ll> pll;

const int INF = 1e9;

const ll LINF = 1e18;

template<class S,class T> ostream& operator << (ostream& out,const pair<S,T>& o){ out << "(" << o.first << "," << o.second << ")"; return out; }

template<class T> ostream& operator << (ostream& out,const vector<T> V){ for(int i = 0; i < V.size(); i++){ out << V[i]; if(i!=V.size()-1) out << " ";} return out; }

template<class T> ostream& operator << (ostream& out,const vector<vector<T> > Mat){ for(int i = 0; i < Mat.size(); i++) { if(i != 0) out << endl; out << Mat[i];} return out; }

template<class S,class T> ostream& operator << (ostream& out,const map<S,T> mp){ out << "{ "; for(auto it = mp.begin(); it != mp.end(); it++){ out << it->first << ":" << it->second; if(mp.size()-1 != distance(mp.begin(),it)) out << ", "; } out << " }"; return out; }



/*

 <url:>

 問題文============================================================

 =================================================================

 解説=============================================================

 ================================================================

 */





ll solve(){

    ll res = 0;

    

    ll N; cin >> N;

    vector<ll> X(N); for(auto& in:X) cin >> in;

    auto tX = X;

    sort(tX.begin(),tX.end());

    ll T = tX[N/2];

    

    for(int i = 0; i < N;i++){

        if(X[i] >= T){

            cout << tX[N/2-1] << endl;

        }else{

            cout << T << endl;

        }

    }

    

    

    return res;

}

int main(void) {

    cin.tie(0); ios_base::sync_with_stdio(false);

    solve();

    return 0;

}


// Optimized solution to the same problem (faster):
#include<stdio.h>

#include<algorithm>

using namespace std;

int a[200010],b[200010];

main(){

    int n,i,x,y;

    scanf("%d",&n);

    for(i=0;i<n;++i)

    {

        scanf("%d",&a[i]);

        b[i]=a[i];

    }

    sort(b,b+n);

    x=b[(n/2)-1];

    y=b[(n/2)];

    if(x==y)

    {

        for(i=1;i<=n;++i)

        {

            printf("%d\n",x);

        }

    }

    else

    {

        for(i=0;i<n;++i)

        {

            if(a[i]<=x)

            {

                printf("%d\n",y);

            }

            else

            {

                printf("%d\n",x);

            }

        }

    }

}


// Fastest known solution for this problem:
// Original C++ solution (slower):
#include <bits/stdc++.h>



using namespace std;

typedef long long ll;

ll MAX_N = 200005;



int main() {

  ll n;

  ll x[MAX_N], y[MAX_N];

  scanf("%lld", &n);

  for (ll i=0; i<n; i++) {

    scanf("%lld", &x[i]);

    y[i] = x[i];

  }

  sort(y, y+n);

  

  ll m = n/2 - 1;

  for (ll i=0; i<n; i++) {

    if (y[m] < x[i]) {

      printf("%lld\n", y[m]);

    } else {

      printf("%lld\n", y[m+1]);

    }

  }

  

  return 0;

}


// Optimized solution to the same problem (faster):
#include<stdio.h>

#include<algorithm>

using namespace std;

int a[200010],b[200010];

main(){

    int n,i,x,y;

    scanf("%d",&n);

    for(i=0;i<n;++i)

    {

        scanf("%d",&a[i]);

        b[i]=a[i];

    }

    sort(b,b+n);

    x=b[(n/2)-1];

    y=b[(n/2)];

    if(x==y)

    {

        for(i=1;i<=n;++i)

        {

            printf("%d\n",x);

        }

    }

    else

    {

        for(i=0;i<n;++i)

        {

            if(a[i]<=x)

            {

                printf("%d\n",y);

            }

            else

            {

                printf("%d\n",x);

            }

        }

    }

}


// Fastest known solution for this problem:
// Original C++ solution (slower):
#include <bits/stdc++.h>

const char nl = '\n';

using namespace std;

using ll = long long;

using ld = long double;

const int N = 1e4+10;



int d[N*2];



int main() {

  ios::sync_with_stdio(0);

  cin.tie(0);

  int k, q; cin >> k >> q;

  for (int i = 0; i < k; i++) {

    cin >> d[i];

  }

  int nk = k;

  while (nk < N) nk += k;

  for (int i = k; i < nk; i++) {

    d[i] = d[i%k];

  }

  k = nk;

  while (q--) {

    int n, x, m; cin >> n >> x >> m;

    n--;

    x %= m;

    ll tot = 0;

    int zcnt = 0;

    for (int i = 0; i < k; i++) {

      tot += (d[i] % m);

      zcnt += (d[i] % m == 0);

    }

    int num_cyc = n / k, rem_cyc = n % k;

    ll ans = num_cyc * k - (x + tot * num_cyc) / m - num_cyc * zcnt;

    //cout << ans << nl;

    x = (x + tot * num_cyc) % m;

    for (int i = 0; i < rem_cyc; i++) {

      int nx = (x + d[i]) % m;

      //cerr << x << " " << nx << nl;

      ans += (x < nx);

      x = nx;

    }

    cout << ans << nl;

  }

}


// Optimized solution to the same problem (faster):
#include <bits/stdc++.h>

const char nl = '\n';

using namespace std;

using ll = long long;

using ld = long double;

const int N = 5050;



int d[N*2];



int main() {

  ios::sync_with_stdio(0);

  cin.tie(0);

  int k, q; cin >> k >> q;

  for (int i = 0; i < k; i++) {

    cin >> d[i];

  }

  /*

  int nk = k;

  while (nk < N) nk += k;

  for (int i = k; i < nk; i++) {

    d[i] = d[i%k];

  }

  k = nk;*/

  while (q--) {

    int n, x, m; cin >> n >> x >> m;

    n--;

    x %= m;

    ll tot = 0;

    int zcnt = 0;

    for (int i = 0; i < k; i++) {

      tot += (d[i] % m);

      zcnt += (d[i] % m == 0);

    }

    int num_cyc = n / k, rem_cyc = n % k;

    ll ans = num_cyc * k - (x + tot * num_cyc) / m - num_cyc * zcnt;

    //cout << ans << nl;

    x = (x + tot * num_cyc) % m;

    for (int i = 0; i < rem_cyc; i++) {

      int nx = (x + d[i]) % m;

      //cerr << x << " " << nx << nl;

      ans += (x < nx);

      x = nx;

    }

    cout << ans << nl;

  }

}


// Fastest known solution for this problem: