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

using namespace std;

typedef long long ll;

#define rep(i, n) for(int i = 0; i < (n); i++)

#define rep1(i, n) for(int i = 1; i <= (n); i++)

#define co(x) cout << (x) << "\n"

#define cosp(x) cout << (x) << " "

#define ce(x) cerr << (x) << "\n"

#define cesp(x) cerr << (x) << " "

#define pb push_back

#define mp make_pair

#define Would

#define you

#define please





int main() {

	cin.tie(0);

	ios::sync_with_stdio(false);





	int N, K;

	cin >> N >> K;

	int h[100000];

	rep(i, N) {

		cin >> h[i];

	}

	sort(h, h + N);



	int saishou = 1e9;

	rep(i, N - K + 1) {

		saishou = min(saishou, h[i + K - 1] - h[i]);

	}

	co(saishou);



	Would you please return 0;

}

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

#include<cstdio>

#include<algorithm>

using namespace std;

typedef long long ll;

#define rep(i, n) for(int i = 0; i < (n); i++)

#define rep1(i, n) for(int i = 1; i <= (n); i++)

#define co(x) cout << (x) << "\n"

#define cosp(x) cout << (x) << " "

#define ce(x) cerr << (x) << "\n"

#define cesp(x) cerr << (x) << " "

#define pb push_back

#define mp make_pair

#define Would

#define you

#define please



const int cm = 1 << 17;

char cn[cm], * ci = cn + cm, ct;

inline char getcha() {

	if (ci - cn == cm) { fread_unlocked(cn, 1, cm, stdin); ci = cn; }

	return *ci++;

}

inline int getint() {

	int A = 0;

	if (ci - cn + 16 > cm) while ((ct = getcha()) >= '0') A = A * 10 + ct - '0';

	else while ((ct = *ci++) >= '0') A = A * 10 + ct - '0';

	return A;

}



void pakuri_sort(int N, int A[]) {

	const int b = 8;

	int tmp[100001];

	rep(k, 4) {

		int kazu[1 << b] = {}, kazu2[1 << b] = {};

		rep(i, N) kazu[A[i] >> k * b & ((1 << b) - 1)]++;

		rep(i, (1 << b) - 1) kazu[i + 1] += kazu[i];

		for (int i = N - 1; i >= 0; i--) tmp[--kazu[A[i] >> k * b & ((1 << b) - 1)]] = A[i];

		k++;

		rep(i, N) kazu2[tmp[i] >> k * b & ((1 << b) - 1)]++;

		rep(i, (1 << b) - 1) kazu2[i + 1] += kazu2[i];

		for (int i = N - 1; i >= 0; i--) A[--kazu2[tmp[i] >> k * b & ((1 << b) - 1)]] = tmp[i];

	}

}



int main() {

	//cin.tie(0);

	//ios::sync_with_stdio(false);





	int N = getint(), K = getint();

	int h[100000];

	rep(i, N) h[i] = getint();

	pakuri_sort(N, h);



	int saishou = 1e9;

	rep(i, N - K + 1) {

		saishou = min(saishou, h[i + K - 1] - h[i]);

	}

	printf("%d", saishou);



	Would you please return 0;

}

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

using namespace std;

typedef long long ll;

#define rep(i, n) for(int i = 0; i < (n); i++)

#define rep1(i, n) for(int i = 1; i <= (n); i++)

#define co(x) cout << (x) << "\n"

#define cosp(x) cout << (x) << " "

#define ce(x) cerr << (x) << "\n"

#define cesp(x) cerr << (x) << " "

#define pb push_back

#define mp make_pair

#define Would

#define you

#define please



const int cm = 1 << 17;

char cn[cm], * ci = cn + cm, ct;

inline char getcha() {

	if (ci - cn == cm) { fread_unlocked(cn, 1, cm, stdin); ci = cn; }

	return *ci++;

}

inline int getint() {

	int A = 0;

	if (ci - cn + 16 > cm) while ((ct = getcha()) >= '0') A = A * 10 + ct - '0';

	else while ((ct = *ci++) >= '0') A = A * 10 + ct - '0';

	return A;

}



int main() {

	cin.tie(0);

	ios::sync_with_stdio(false);





	int N = getint(), K = getint();

	int h[100000];

	rep(i, N) h[i] = getint();

	sort(h, h + N);



	int saishou = 1e9;

	rep(i, N - K + 1) {

		saishou = min(saishou, h[i + K - 1] - h[i]);

	}

	co(saishou);



	Would you please return 0;

}

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

#include<cstdio>

#include<algorithm>

using namespace std;

typedef long long ll;

#define rep(i, n) for(int i = 0; i < (n); i++)

#define rep1(i, n) for(int i = 1; i <= (n); i++)

#define co(x) cout << (x) << "\n"

#define cosp(x) cout << (x) << " "

#define ce(x) cerr << (x) << "\n"

#define cesp(x) cerr << (x) << " "

#define pb push_back

#define mp make_pair

#define Would

#define you

#define please



const int cm = 1 << 17;

char cn[cm], * ci = cn + cm, ct;

inline char getcha() {

	if (ci - cn == cm) { fread_unlocked(cn, 1, cm, stdin); ci = cn; }

	return *ci++;

}

inline int getint() {

	int A = 0;

	if (ci - cn + 16 > cm) while ((ct = getcha()) >= '0') A = A * 10 + ct - '0';

	else while ((ct = *ci++) >= '0') A = A * 10 + ct - '0';

	return A;

}



void pakuri_sort(int N, int A[]) {

	const int b = 8;

	int tmp[100001];

	rep(k, 4) {

		int kazu[1 << b] = {}, kazu2[1 << b] = {};

		rep(i, N) kazu[A[i] >> k * b & ((1 << b) - 1)]++;

		rep(i, (1 << b) - 1) kazu[i + 1] += kazu[i];

		for (int i = N - 1; i >= 0; i--) tmp[--kazu[A[i] >> k * b & ((1 << b) - 1)]] = A[i];

		k++;

		rep(i, N) kazu2[tmp[i] >> k * b & ((1 << b) - 1)]++;

		rep(i, (1 << b) - 1) kazu2[i + 1] += kazu2[i];

		for (int i = N - 1; i >= 0; i--) A[--kazu2[tmp[i] >> k * b & ((1 << b) - 1)]] = tmp[i];

	}

}



int main() {

	//cin.tie(0);

	//ios::sync_with_stdio(false);





	int N = getint(), K = getint();

	int h[100000];

	rep(i, N) h[i] = getint();

	pakuri_sort(N, h);



	int saishou = 1e9;

	rep(i, N - K + 1) {

		saishou = min(saishou, h[i + K - 1] - h[i]);

	}

	printf("%d", saishou);



	Would you please return 0;

}

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



using namespace std;



vector<int> h(100010);



int main()

{

  int N, K; cin >> N >> K;

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

    cin >> h[i];

  }



  sort(h.begin(), h.begin() + N);



  int ans = 1e9;

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

    ans = min(ans, h[i+K-1] - h[i]);

  }



  cout << ans << endl;

}

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



using namespace std;



int main()

{

  int N, K; cin >> N >> K;

  vector<int> h(N);

  for (int i = 0; i < N; ++i) cin >> h[i];



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



  int ans = 1e9;

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

    ans = min(ans, h[i+K-1]-h[i]);

  }



  cout << ans;

}

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

#include<vector>

#include<algorithm>

#include<cctype>

#include<utility>

#include<string>

#include<cmath>

#include<cstring>

#include<queue>

#include<map>

#include<climits>

 

#define REP(i, n) for(int i = 0;i < n;i++)

#define REPR(i, n) for(int i = n;i >= 0;i--)

#define FOR(i, m, n) for(int i = m;i < n;i++)

#define FORR(i, m, n) for(int i = m;i >= n;i--)

#define SORT(v, n) sort(v, v+n);

#define VSORT(v) sort(v.begin(), v.end());

#define llong long long

#define pb(a) push_back(a)

using namespace std;

typedef pair<int, int> P;

typedef long long int ll;

typedef pair<ll,ll> LLP;

#define INF 10000000000007

 

#define ARRAY_MAX 100005

 

int main(){

 

    ll n,k;

    cin >> n >> k;

    vector<ll> a(ARRAY_MAX);

    REP(i,n){

        cin >> a[i];

    }

    sort(a.begin(),a.begin()+n);

    

    ll mini = INF;

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

        mini = min(mini,a[i+k-1]-a[i]);

    }

    cout << mini << endl;

 

 

 

 

    return 0;

}

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

#include<vector>

#include<algorithm>

#include<cctype>

#include<utility>

#include<string>

#include<cmath>

#include<cstring>

#include<queue>

#include<map>

#include<climits>

#include<set>

 

#define REP(i, n) for(int i = 0;i < n;i++)

#define REPR(i, n) for(int i = n;i >= 0;i--)

#define FOR(i, m, n) for(int i = m;i < n;i++)

#define FORR(i, m, n) for(int i = m;i >= n;i--)

#define SORT(v, n) sort(v, v+n);

#define VSORT(v) sort(v.begin(), v.end());

#define llong long long

#define pb(a) push_back(a)

using namespace std;

typedef pair<int, int> P;

typedef long long int ll;

typedef pair<ll,ll> LLP;

#define INF 1000000007

 

#define ARRAY_MAX 100005

 

int main(){



    int n,k;

    cin >> n >> k;

    vector<int> a(n);

    REP(i,n){

        cin >> a[i];

    }

    VSORT(a);

    int mini = INF;

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

        mini = min(mini,a[i+k-1]-a[i]);

    }

    cout << mini << endl;



    return 0;

}

// Fastest known solution for this problem:
// Original C++ solution (slower):
/*Bismillahir Rahmanir Rahim*/

#include<bits/stdc++.h>

using namespace std;

int main()

{

    long long int a[100007],i,j,N,K,l;

    cin>>N>>K;

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

        cin>>a[i];

    sort(a,a+N);

    l=a[K-1]-a[0];

    for(i=0; i<N-K+1; i++)

    {

        j=a[i+K-1]-a[i];

        if(j<l)

            l=j;

    }

    cout<<l<<endl;

    return 0;

}


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

#include<stdlib.h>

int a[100005];

int inc(const void *a, const void *b)

{

    return *(int *)a-*(int *)b;

}

int main()

{

	int n,m,min=-1;

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

	for(int i=0;i<n;i++)scanf("%d",&a[i]);

	qsort(a,n,sizeof(int),inc);

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

	{

		if(min==-1)min=a[i+m-1]-a[i];

		if(min>a[i+m-1]-a[i])min=a[i+m-1]-a[i];

	}

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

}

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

const long long INF = 1LL << 60;

using namespace std;



int main() {

    int N, K;

    cin >> N >> K;

    

    vector<long long> h(N);

    for (int i = 0; i < h.size(); ++i) cin >> h[i];



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



    long long dp[100010];

    for (int i = 0; i < 100010; ++i) dp[i]= INF;

    for (int i = 0; i < h.size() - (K - 1); ++i) dp[i] = h[i+(K-1)] - h[i];

    

    long long ans = INF;

    for (int i = 0; i < 100010; ++i) ans = min(ans, dp[i]);



    cout << ans << endl;

    return 0;

}

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

const long long INF = 1LL << 60;

using namespace std;



int main() {

    int N, K;

    cin >> N >> K;



    vector<long long> h(N);

    for (int i = 0; i < h.size(); ++i) cin >> h[i];



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



    long long ans = INF;

    for (int i = 0; i < h.size() - (K - 1); ++i) ans = min(ans, h[i+(K-1)] - h[i]);



    cout << ans << endl;

    return 0;

}

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

using namespace std;

#include <stdlib.h>

int asc(const void *a, const void *b) {

   return *(int *)a - *(int *)b;

}

#define MIN(a,b) ((a)<(b)?(a):(b))

int main(void) {

   int N, K;

   int ans = 1000000010;

   int L[1000000];

   cin >> N;

   cin >> K;

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

      cin >> L[i];

   }

   qsort(L,N,sizeof (int), asc);

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

      ans = MIN(ans, L[i+K-1] - L[i]);

   }

   cout << ans << endl;

  return 0;

}

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

#include <stdlib.h>

#define MIN(a,b) ((a)<(b)?(a):(b))

#define ABS(a) ((a)>(0)?(a):-(a))



int asc(const void *a, const void *b) {

   return *(int *)a - *(int *)b;

}



int main(void){

   int N,K;

   int L[100000+1];

   int ans = 1000000010;

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

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

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

   }

   qsort(L,N,sizeof (int), asc);

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

      ans = MIN(ans,ABS(L[i]-L[i+(K-1)]));

   }

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

   return 0;

}


// Fastest known solution for this problem:
// Original C++ solution (slower):
#define _CRT_SECURE_NO_WARNINGS

#include <iostream>

#include <sstream>

#include <iomanip>

#include <cstdio>

#include <cstdlib>

#include <cmath>

#include <cctype>

#include <cstring>

#include <vector>

#include <list>

#include <queue>

#include <deque>

#include <stack>

#include <map>

#include <set>

#include <algorithm>

#include <iterator>

#include <bitset>

#include <ctime>

#include<complex>

using namespace std;



#define FOR(i,a,b) for (int i = (a); i < (b); i++)

#define RFOR(i,b,a) for (int i = (b)-1; i >= (a); i--)

#define ITER(it,a) for (__typeof(a.begin()) it = a.begin(); it != a.end(); it++)

#define FILL(a,value) memset(a, value, sizeof(a))



#define SZ(a) (int)a.size()

#define ALL(a) a.begin(), a.end()

#define PB push_back

#define MP make_pair



typedef long long LL;

typedef vector<int> VI;

typedef pair<int, int> PII;



const double PI = acos(-1.0);

const int INF = 1000 * 1000 * 1000 + 7;

const LL LINF = INF * (LL)INF;



const int MAX = 1000 * 100 + 47;

const int MOD = 1000 * 1000 * 1000 + 7;



LL T[MAX];

LL A[MAX];

LL Q[MAX];

int sz;



int main()

{

	//freopen("in.txt", "r", stdin);

	//freopen("out.txt", "w", stdout);

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

	int n, q;

	cin >> n >> q;

	if (q == 0)

	{

		FOR(i, 0, n) cout << "1\n";

		return 0;

	}



	FOR(i, 0, q)

	{

		LL a;

		cin >> a;

		while (sz && Q[sz - 1] >= a) sz--;

		Q[sz++] = a;

	}

	

	//cout << sz << endl;

	//FOR(i, 0, sz) cout << Q[i] << " ";

	//cout << endl;

	T[sz - 1] = 1;

	LL cnt = min(Q[0], (LL)n);



	RFOR(i, sz, 0)

	{

		LL a = Q[i];

		while (1)

		{

			int ind = lower_bound(Q, Q + sz, a) - Q;

			if (ind == 0) break;

			ind--;



			T[ind] += T[i] * (a / Q[ind]);

			a %= Q[ind];

		}



		A[cnt - 1] += (a / cnt) * T[i];

		if (a % cnt) A[a % cnt - 1] += T[i];

	}



	//FOR(i, 0, n) cout << A[i] << " ";

	//cout << endl;

	RFOR(i, n - 1, 0)

	{

		A[i] += A[i + 1];

	}



	FOR(i, 0, n) cout << A[i] << " \n";

	cout << endl;

}

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

#include <algorithm>

using namespace std;

typedef long long ll;

const int N = 100100;

ll q[N],f[N],tag[N],x;

int n,Q,tail;

void solve(ll d,ll v) {

    if(d==0) return ;

    int j=upper_bound(q+1,q+tail+1,d)-q-1;

    if(j==0) tag[1]+=v,tag[d+1ll]-=v;

    else f[j]+=d/q[j]*v,solve(d%q[j],v);

}

int main() {

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

    q[++tail]=(ll)n;

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

        scanf("%lld",&x);

        while(tail&&q[tail]>=x) tail--;

        q[++tail]=x;

    }

    f[tail]=1;

    for(int i=tail;i>1;i--) {

        f[i-1]+=q[i]/q[i-1]*f[i];

        solve(q[i]%q[i-1],f[i]);

    }

    tag[1]+=f[1],tag[q[1]+1ll]-=f[1];

    for(int i=1;i<=n;i++) tag[i]+=tag[i-1],printf("%lld\n",tag[i]);

}

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

#include <iterator>

#include <iostream>

#include <cstring>

#include <cstdio>

#include <vector>

#include <stack>

#define REDIRECT(x) freopen(x".in", "r", stdin), freopen(x".out", "w", stdout)

#define CLOSEALL() fclose(stdin), fclose(stdout)

using namespace std;

typedef long long i64;

const int MAXN = 1e5 + 10;

const int MAXQ = 1e5 + 10;



int N, Q;



int monoTop;

i64 monoStk[MAXN], tmp[MAXN], ans[MAXN];



void solve(i64 query, i64 delta)

{

	int index = lower_bound(monoStk + 1, monoStk + monoTop + 1, query) - monoStk - 1;

	if(index <= 0)

		ans[1] += delta, ans[query + 1] -= delta;

	else

		tmp[index] += delta * (query / monoStk[index]),

		solve(query % monoStk[index], delta);

}



int main()

{

	//REDIRECT("seq");



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

	monoStk[++monoTop] = N;

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

	{

		i64 t;

		scanf("%lld", &t);



		while(monoTop && t < monoStk[monoTop])

			monoTop--;

		monoStk[++monoTop] = t;

	}



	tmp[monoTop] = 1;

	for(int i = monoTop; i > 0; i--)

		solve(monoStk[i], tmp[i]);

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

		ans[i] += ans[i-1], printf("%lld\n", ans[i]);



	CLOSEALL();

	return 0;

}


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

#include <algorithm>

using namespace std;

typedef long long ll;

const int N = 100100;

ll q[N],f[N],tag[N],x;

int n,Q,tail;

void solve(ll d,ll v) {

    if(d==0) return ;

    int j=upper_bound(q+1,q+tail+1,d)-q-1;

    if(j==0) tag[1]+=v,tag[d+1ll]-=v;

    else f[j]+=d/q[j]*v,solve(d%q[j],v);

}

int main() {

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

    q[++tail]=(ll)n;

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

        scanf("%lld",&x);

        while(tail&&q[tail]>=x) tail--;

        q[++tail]=x;

    }

    f[tail]=1;

    for(int i=tail;i>1;i--) {

        f[i-1]+=q[i]/q[i-1]*f[i];

        solve(q[i]%q[i-1],f[i]);

    }

    tag[1]+=f[1],tag[q[1]+1ll]-=f[1];

    for(int i=1;i<=n;i++) tag[i]+=tag[i-1],printf("%lld\n",tag[i]);

}

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

#include<cstring>

#include<algorithm>

#include<map>

const int N=3e5+5;

using namespace std;

typedef long long ll;

typedef map<ll,ll>::iterator mit;

int n,q;

ll p[N];

map<ll,ll> mp;

ll cnt[N];

int main()

{

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

    if(q==0){

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

            puts("1");

        return 0;

    }

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

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

    mp[p[q]]++;

    p[0]=n;

    for(int i=q-1;i>=0;i--){

        while(mp.rbegin()->first>p[i]){

            mit it=mp.end();

            it--;

            mp[it->first%p[i]]+=it->second;

            mp[p[i]]+=it->second*(it->first/p[i]);

            mp.erase(it);

        }

    }

    for(mit it=mp.begin();it!=mp.end();it++)

        cnt[it->first]+=it->second;

    for(int i=n;i>=1;i--)

        cnt[i]=cnt[i]+cnt[i+1];

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

        printf("%lld\n",cnt[i]);

}


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

#include <algorithm>

using namespace std;

typedef long long ll;

const int N = 100100;

ll q[N],f[N],tag[N],x;

int n,Q,tail;

void solve(ll d,ll v) {

    if(d==0) return ;

    int j=upper_bound(q+1,q+tail+1,d)-q-1;

    if(j==0) tag[1]+=v,tag[d+1ll]-=v;

    else f[j]+=d/q[j]*v,solve(d%q[j],v);

}

int main() {

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

    q[++tail]=(ll)n;

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

        scanf("%lld",&x);

        while(tail&&q[tail]>=x) tail--;

        q[++tail]=x;

    }

    f[tail]=1;

    for(int i=tail;i>1;i--) {

        f[i-1]+=q[i]/q[i-1]*f[i];

        solve(q[i]%q[i-1],f[i]);

    }

    tag[1]+=f[1],tag[q[1]+1ll]-=f[1];

    for(int i=1;i<=n;i++) tag[i]+=tag[i-1],printf("%lld\n",tag[i]);

}

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

using namespace std;

typedef long long LL;

const int N = 100010;

LL n, q, x, w[N], p[N];

stack<LL> s;

vector<LL> v;

void solve(LL pos, LL W) {

    int x = lower_bound(v.begin(), v.end(), pos) - v.begin() - 1;

    if (x<0) {

        p[1] += W;

        p[pos+1] -= W;

        return;

    }

    w[x] += pos / v[x] * W;

    solve(pos % v[x], W);

}

int main() {

    scanf("%lld%lld", &n, &q);

    s.push(n);

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

        scanf("%lld", &x);

        while (s.size() && s.top() >= x) s.pop();

        s.push(x);

    }

    while (s.size()) {

        v.push_back(s.top());

        s.pop();

    }

    reverse(v.begin(), v.end());

    w[v.size() - 1] = 1;

    for (int i = v.size() - 1; ~i; i--) solve(v[i], w[i]);

    for (int i = 1; i <= n; i++) p[i] += p[i - 1];

    for (int i = 1; i <= n; i++) printf("%lld\n", p[i]);

    return 0;

}

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

#include <algorithm>

using namespace std;

typedef long long ll;

const int N = 100100;

ll q[N],f[N],tag[N],x;

int n,Q,tail;

void solve(ll d,ll v) {

    if(d==0) return ;

    int j=upper_bound(q+1,q+tail+1,d)-q-1;

    if(j==0) tag[1]+=v,tag[d+1ll]-=v;

    else f[j]+=d/q[j]*v,solve(d%q[j],v);

}

int main() {

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

    q[++tail]=(ll)n;

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

        scanf("%lld",&x);

        while(tail&&q[tail]>=x) tail--;

        q[++tail]=x;

    }

    f[tail]=1;

    for(int i=tail;i>1;i--) {

        f[i-1]+=q[i]/q[i-1]*f[i];

        solve(q[i]%q[i-1],f[i]);

    }

    tag[1]+=f[1],tag[q[1]+1ll]-=f[1];

    for(int i=1;i<=n;i++) tag[i]+=tag[i-1],printf("%lld\n",tag[i]);

}

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

#include <iostream>

#include <algorithm>

#include <cstring>

#include <cmath>

#define ll long long

using namespace std; 

const int N=200010;

ll n,num,m,x; 

ll a[N],f[N],s[N]; 

void solve(ll x,ll k){

	if (x<a[1]){

		s[x]+=k;

		return;

	}

	ll l=1,r=num,y;

	while (l<=r){

		ll mid=(l+r)/2;

		if (a[mid]<=x){

			y=mid;

			l=mid+1;

		}else r=mid-1;

	}

	f[y]+=k*(x/a[y]);

	x=x%a[y];

	if (x) solve(x,k);

}

int main(){

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

	num=1;

	a[1]=n;

	for (ll i=1; i<=m; i++){

		scanf("%lld",&x);

		while (x<=a[num]&&num)

			--num;

		num++;

		a[num]=x;

	}

	f[num]=1;

	for (ll i=num-1; i>=1; i--){

		f[i]+=f[i+1]*(a[i+1]/a[i]);

		solve(a[i+1]%a[i],f[i+1]);

	}

	for (ll i=a[1]; i>=1; i--)

		s[i]+=s[i+1];

	for (ll i=1; i<=a[1]; i++)

		s[i]+=f[1];

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

		printf("%lld\n",s[i]);

	return 0;

}

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

#include <algorithm>

using namespace std;

typedef long long ll;

const int N = 100100;

ll q[N],f[N],tag[N],x;

int n,Q,tail;

void solve(ll d,ll v) {

    if(d==0) return ;

    int j=upper_bound(q+1,q+tail+1,d)-q-1;

    if(j==0) tag[1]+=v,tag[d+1ll]-=v;

    else f[j]+=d/q[j]*v,solve(d%q[j],v);

}

int main() {

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

    q[++tail]=(ll)n;

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

        scanf("%lld",&x);

        while(tail&&q[tail]>=x) tail--;

        q[++tail]=x;

    }

    f[tail]=1;

    for(int i=tail;i>1;i--) {

        f[i-1]+=q[i]/q[i-1]*f[i];

        solve(q[i]%q[i-1],f[i]);

    }

    tag[1]+=f[1],tag[q[1]+1ll]-=f[1];

    for(int i=1;i<=n;i++) tag[i]+=tag[i-1],printf("%lld\n",tag[i]);

}

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

#include<algorithm>

#include<map>

using namespace std;



typedef long long ll;

const int MAXN=1e5+5;



int n,m;

ll ans[MAXN],q[MAXN];

map<ll,ll> a;

map<ll,ll>::iterator it;



int main(){



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

    if(m==0){

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

        return 0;

    }

    for(int i=1;i<=m;i++) scanf("%lld",&q[i]);

    a[q[m]]++; q[0]=n;

    for(int i=m-1;i>=0;i--)

        while(a.rbegin()->first>q[i]){

            it=a.end(); it--;

            a[it->first%q[i]]+=it->second;

            a[q[i]]+=it->second*(it->first/q[i]);

            a.erase(it);

        }

    for(it=a.begin();it!=a.end();it++) ans[it->first]+=it->second;

    for(int i=n;i>=1;i--) ans[i]+=ans[i+1];

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

        printf("%lld\n",ans[i]);



    fclose(stdin);

    fclose(stdout);

}


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

#define LL long long

#define maxn 100005

int n,q,r;

LL a[maxn],cnt[maxn],app[maxn],ans[maxn];

int BS(int l,int r,LL k)

{

	while(l+1<r)

	{

		int mid=(l+r)>>1;

		if(a[mid]<=k) l=mid;

		else r=mid;

	}

	return r;

}

int main()

{

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

	a[q=1]=n;

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

	{

		LL x;

		scanf("%lld",&x);

		while(q&&a[q]>=x) q--;

		a[++q]=x;

	}

	app[q]=1;

	for(int i=q;i;i--)

	{

		LL l=a[i];

		int p=BS(1,i-1,l);

		while(p)

		{

			app[p]+=l/a[p]*app[i];

			l%=a[p];

			p=BS(1,p-1,l);

		}

		ans[l]+=app[i];

	}

	for(int i=n;i;i--) ans[i]+=ans[i+1];

	for(int i=1;i<=n;i++) printf("%lld\n",ans[i]);

}

// Fastest known solution for this problem: