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

#include <string>

#include <set>

#include <cmath>

#include <vector>

#include <algorithm>

using namespace std;

using ll =long long;

typedef long double ld;

const long double eps=1e-12;

const int maxn=(int)1e5+10;



ld p[maxn];



void mypow(){

    p[0]=1;

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

        p[i]=p[i-1]*0.5;

    }

}



int main()

{

    int n,m;

    ld sum;

    mypow();

    while(scanf("%d%d",&n,&m)!=EOF){

        sum=0;

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

            ll cnt=0,r=i;

            while(r<m) r*=2,cnt++;

            //cout << cnt << endl;

            sum+=(ld)((1.0/n)*p[cnt]);

        }

        printf("%.12Lf",sum);

    }

    return 0;

}

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

#include <string>

#include <set>

#include <cmath>

#include <vector>

#include <algorithm>

using namespace std;

using ll =long long;

typedef long double ld;

const long double eps=1e-12;



ld mypow(ld a,ll i){

    if(i==0) return 1;

    ld t=mypow(a,i>>1);

    t*=t;

    if(i&1) t=(ld)(t*a);

    return t;

}



int main()

{

    int n,m;

    ld sum;

    while(scanf("%d%d",&n,&m)!=EOF){

        sum=0;

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

            ll r=i,cnt=0;

            while(r<m) r*=2,cnt++;

            //cout << cnt << endl;

            sum+=(ld)((1.0/n)*mypow(1.0/2,cnt));

        }

        printf("%.12Lf",sum);

    }

    return 0;

}

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


#include<iostream>

#include<vector>

#include<string>

#include<tuple>

#include<algorithm>

#include<iomanip>



using namespace std;



long Lcm(long, long);

long Gcd(long, long);



int main(){

    long N,K;

    cin >> N >> K;

    vector<long> denomList; //確率の分母を保存



    //出た目の場合ごとに回す

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

    {

        long denom = N;  //確率の分母

        long x = i;

        while(x<K)

        {

            denom *= 2;

            x *= 2;

        }

        denomList.emplace_back(denom);

    }

    //それぞれの確率から出力する確率を計算する

    long lcm = 1;

    for(int i=0; i<denomList.size(); i++)

    {

        lcm = Lcm(lcm, denomList[i]);

    }



    long mol = 0;



    for(int i=0; i<denomList.size(); i++)

    {

        mol += (lcm/denomList[i]);

    } 



    long double output = 0.0000000000;

    output = static_cast<long double>(mol) / static_cast<long double>(lcm);



    cout << fixed << setprecision(10) << output << endl;

}



//2数の最大公約数を見つける

long Gcd(long a, long b)

{

    if(a < b)

    {

        return Gcd(b, a);

    }

    else if(b > 0)

    {

        return Gcd(b, a % b);

    }

    else

    {

        return a;

    }

}



//2数の最小公倍数を見つける

long Lcm(long a, long b)

{

    return a / Gcd(a, b) * b;

}

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

#define _GLIBCXX_DEBUG

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

using namespace std;

using ll = long long;

const int INF = 1001001001;

const int MOD = 1000000007;

typedef long long ll;



template<typename T> void print(const T & v);





int main() {

    ll N, K;

    cin >> N >> K;

    double ans = 0.0;

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

        double p = 1.0;

        ll x = i;

        while(x < K){

            p /= 2.0;

            x *= 2;

        }

        ans += p;

    }

    ans /= N;

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

    return 0;

}





// Use For Debug

template <typename T>

void print(T const & v){

    for(int i = 0; i < v.size(); i++){

        if(i) cout << " ";

        cout << v[i];

    }

    cout << endl;

}


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

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

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

using namespace std;

const long long MOD = 1e9 + 7;

const long long INF = 1e12;

const int inf = 1e9;

typedef long long ll;

typedef pair<ll,int> P;

typedef set<int> S;

int main(){

    double n,k;

    cin>>n>>k;

    vector<double> vd;

    //cout<<1/4<<endl;

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

        //cout<<i<<" ";

        double p = (double)(1/n);

        //cout<<p<<" "<<(double)(1/n)<<" ";

        int now = i;

        //cout<<"bool"<<endl;

        //cout<<now<<" "<<k<<endl;

        //cout<<endl;

        while(now<k){

            //cout<<"ei"<<endl;

            p/=2;

            now*=2;

        }

        vd.push_back(p);

        //cout<<p<<endl;

    }

    double ans = 0;

    for(auto u : vd){

        ans+= u;

    }

    printf("%.10lf\n",ans);

    return 0;

}

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

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

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

using namespace std;

const long long MOD = 1e9 + 7;

const long long INF = 1e12;

const int inf = 1e9;

const int mod = 1e9+7;

typedef long long ll;

typedef pair<ll,int> P;

typedef set<int> S;

int main(){

    int n,k;

    cin >> n >> k;

    double ans = 0;

    rep(i,n){

        double now = 1.0/(n);

        int poi = i+1;

        while(poi<k){

            now/=2.0;

            poi*=2;

        }

        ans += now;

    }

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

    return 0;

}

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

#include<cmath>

#include<iomanip>

using namespace std;



int main(){

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

	long double ans = 0;

	long double bunsu = 0, bunsi = 0;

	int p1 = 0;



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

		int p = 1, tmp = i*2;

		for(int j = 0; j < 20; ++j){

			if(tmp >= K) break;

			tmp *= 2;

			p++;

		}



		if(i > K-1) p = 0;

		if(i ==1) p1 = p;

		

		// cout << p << endl;



		bunsu += (long double)pow(10, 13) / pow(2, p);

		bunsi += pow(2, p1-p);

	}



	// cout << bunsi << endl;



	bunsi /= (long double)pow(2, p1);

	bunsi /= (long double)N;



	// bunsu /= (long double)N;

	// ans = (long double)bunsu / pow(10, 13);



	cout << fixed << setprecision(10) << bunsi << endl;



	return 0;

}


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

#include<cmath>

#include<iomanip>



using namespace std;



typedef long long ll;

typedef long double ld;



int main(){

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

	double ans = 0;



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

		double tmp = 1.0/N;

		int now = i, m = 0;

		while(now<K){

			now*=2;

			tmp/=2;

		}

		// tmp = 1.0 / pow(2, m) / (double)N;



		ans += tmp;

	}



	cout << fixed << setprecision(12) << ans << endl;



	return 0;

}


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



#define pb push_back

#define eb emplace_back



using namespace std;



using vi = vector<int>;

using ll = long long;



int main(){

    ios :: sync_with_stdio(false);

    cout.precision(12);

    double n, k;

    cin >> n >> k;





//    // cerr << x << endl;



//     long double r = pow(2, n) - 1.0;

//     long double b = pow(2, x);

//     long double result = r/n;

//     result/=b;



    long double result=0;

    double p = 1.0/n;

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

        double x = k/i;

        int l = ceil(log2(x));

       // cerr << "L = " << l << endl;

        if(l>0)

            result+= p * (1/pow(2, l));

        else

            result+=p;

    }

    //result/=n;

    cout << result << endl;



    return 0;

}


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

#include<iomanip>

using namespace std;

int main()

{

	int n;

	int k;

	cin>>n>>k;

	double ans=0.0;

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

	{

		double res=(double)(1.0/n);

		int sum=i;

		while(sum<k)

		{

			sum*=2;

			res*=0.5;

		}

		ans+=res;

	}

	cout<<fixed<<setprecision(12)<<ans<<endl;

	return 0;

}

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

using namespace std;

const int N=100010;

int n,m;

double ans=0,power[N];

int main()

{

	cin>>n>>m;

	double tmp=0.5;

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

	{

		power[i]=tmp;

		tmp/=2.0;

	}

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

	{

		int cnt=0,now=i;

		while(now<m)now*=2,++cnt;

		if(!cnt)ans+=1.0/n;

		else ans+=1.0/n*power[cnt];

	}

	printf("%.12lf\n",ans);

}

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

using namespace std;



int main(){

	int a,b;double cnt=0;

	cin>>a>>b;

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

		double tot=1.0/a;int now=i;

		while(now<b){

			now*=2;//翻倍 

			tot/=2;//几率减半 

		}

		cnt+=tot;

	}

	cout<<fixed<<setprecision(12)<<cnt<<endl;

	return 0;

}




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

using namespace std;

typedef long long ll;

const ll inf=1e17;

int n,cnt[10],p[10];ll w;;

struct product{ll v,p;}pro[110],qian[10][110];

inline bool cmp(product a,product b){return a.v!=b.v?a.v<b.v:a.p>b.p;}

int main()

{

int i,j;ll xiao=inf;

scanf("%d%lld",&n,&w);

for (i=1;i<=n;i++) scanf("%lld%lld",&pro[i].v,&pro[i].p),xiao=min(xiao,pro[i].v);

sort(pro+1,pro+n+1,cmp);

for (i=1;i<=n;i++) qian[pro[i].v-xiao][++p[pro[i].v-xiao]]=pro[i];

for (i=0;i<4;i++) for (j=1;j<=p[i];j++) qian[i][j].p+=qian[i][j-1].p;

ll a,b,c,d,da=0;

for (a=0;a<=p[0];a++)

for (b=0;b<=p[1];b++)

for (c=0;c<=p[2];c++)

for (d=0;d<=p[3];d++) 

if (a*xiao+b*(xiao+1)+c*(xiao+2)+d*(xiao+3)<=w) da=max(da,qian[0][a].p+qian[1][b].p+qian[2][c].p+qian[3][d].p);

printf("%lld",da); 

}

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

#include <algorithm>

using namespace std;

const int maxn = 105;

typedef long long ll;

int n, m, w[maxn], v[maxn];

int cnt[4];

ll val[4][maxn];

int main() {

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

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

		scanf("%d %d", w + i, v + i);

		val[w[i] - w[1]][++cnt[w[i] - w[1]]] = v[i];

	}

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

		sort(val[i] + 1, val[i] + 1 + cnt[i]);

		reverse(val[i] + 1, val[i] + 1 + cnt[i]);

		for (int j = 1; j <= cnt[i]; j++) {

			val[i][j] += val[i][j - 1];

		}

	}

	ll ans = 0;

	for (int i0 = 0; i0 <= cnt[0]; i0++) {

		for (int i1 = 0; i1 <= cnt[1]; i1++) {

			for (int i2 = 0; i2 <= cnt[2]; i2++) {

				for (int i3 = 0; i3 <= cnt[3]; i3++) {

					if (1ll * i0 * w[1] + 1ll * i1 * (w[1] + 1) + 1ll * i2 * (w[1] + 2) + 1ll * i3 * (w[1] + 3) <= m && val[0][i0] + val[1][i1] + val[2][i2] + val[3][i3] > ans) {

						ans = val[0][i0] + val[1][i1] + val[2][i2] + val[3][i3];

					}

				}

			}

		}

	}

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

	return 0;

}

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



using namespace std;



typedef long long ll;



const int INF = 1e9;

const ll LLINF = 1e18;

const ll MOD = (ll)1e9 + 7;



int main()

{

  int N, LIM; scanf("%d %d", &N, &LIM);

  vector<ll> W(N), V(N);

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

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

  }



  // vector<vector<ll>> dp(N + 5, vector<ll>(305, 0));

  // ll diff_sum = 0;

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

  //   ll diff = W[i] - W[0];

  //   for (int j = i + 1; j > 0; --j) {

  //     for (int k = diff_sum; k >= 0; --k) {

  //       dp[j][k + diff] = max(dp[j][k + diff], dp[j - 1][k] + V[i]);

  //     }

  //   }

  //   diff_sum += diff;

  // }

  vector<vector<vector<ll>>> dp(N + 5, vector<vector<ll>>(N + 5, vector<ll>(305, 0)));

  ll diff_sum = 0;

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

    ll diff = W[i] - W[0];

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

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

        dp[i + 1][j][k] = dp[i][j][k];

        if (k - diff >= 0) {

          dp[i + 1][j][k] = max(dp[i + 1][j][k], dp[i][j - 1][k - diff] + V[i]);

        }

      }

    }

  }

  ll ans = 0;

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

    for (int j = 0; j <= 300; ++j) {

      if (W[0] * i + j <= LIM) {

        ans = max(ans, dp[N][i][j]);

      }

    }

  }



  // ll ans = 0;

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

  //   for (int j = 0; j <= diff_sum; ++j) {

  //     if (W[0] * i + j <= LIM) {

  //       ans = max(ans, dp[i][j]);

  //     }

  //   }

  // }

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



  return 0;

}


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



using namespace std;



typedef long long ll;



const int INF = 1e9;

const ll LLINF = 1e18;

const ll MOD = (ll)1e9 + 7;



int main()

{

  int N, LIM; scanf("%d %d", &N, &LIM);

  vector<int> W(N), V(N);

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

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

  }



  vector<vector<int>> dp(N + 5, vector<int>(305, 0));



  int sum = 0;

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

    int diff = W[i] - W[0];

    sum += diff;

    for (int j = sum; j >= 0; --j) {

      if (j - diff < 0) { continue; }

      for (int p = i + 1; p >= 1; --p) {

        dp[p][j] = max(dp[p][j], dp[p - 1][j - diff] + V[i]);

      }

    }

  }



  int ans = 0;

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

    for (int j = 0; j <= sum; ++j) {

      if (1LL* i * W[0] + j <= LIM) {

        ans = max(ans, dp[i][j]);

      }

    }

  }

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

  return 0;

}


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



using namespace std;



typedef long long ll;



const int INF = 1e9;

const ll LLINF = 1e18;

const ll MOD = (ll)1e9 + 7;



int main()

{

  int N, LIM; scanf("%d %d", &N, &LIM);

  vector<int> W(N), V(N);

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

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

  }



  vector<vector<vector<int>>> dp(N + 5, vector<vector<int>>(N + 5, vector<int>(300 + 5, 0)));



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

    int diff = W[i - 1] - W[0];

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

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

        dp[i][j][k] = dp[i - 1][j][k];

        if (k - diff >= 0) {

          dp[i][j][k] = max(dp[i][j][k], dp[i - 1][j - 1][k - diff] + V[i - 1]);

        }

      }

    }

  }



  int ans = 0;

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

    for (int j = 0; j <= 300; ++j) {

      if (1LL * W[0] * i + j <= LIM) {

        ans = max(ans, dp[N][i][j]);

      }

    }

  }

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

  return 0;

}


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



using namespace std;



typedef long long ll;



const int INF = 1e9;

const ll LLINF = 1e18;

const ll MOD = (ll)1e9 + 7;



int main()

{

  int N, LIM; scanf("%d %d", &N, &LIM);

  vector<int> W(N), V(N);

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

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

  }



  vector<vector<int>> dp(N + 5, vector<int>(305, 0));



  int sum = 0;

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

    int diff = W[i] - W[0];

    sum += diff;

    for (int j = sum; j >= 0; --j) {

      if (j - diff < 0) { continue; }

      for (int p = i + 1; p >= 1; --p) {

        dp[p][j] = max(dp[p][j], dp[p - 1][j - diff] + V[i]);

      }

    }

  }



  int ans = 0;

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

    for (int j = 0; j <= sum; ++j) {

      if (1LL* i * W[0] + j <= LIM) {

        ans = max(ans, dp[i][j]);

      }

    }

  }

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

  return 0;

}


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

#include <algorithm>

#include <cstring>

#include <cmath>

#include <vector>

#include <set>

#include <queue>

#include <map>

#include <string>



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

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

#define pb push_back

#define mp make_pair

#define bg begin()

#define en end()

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

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



using namespace std;



typedef long long ll;

typedef long double ld;



using P = pair<int, int>;



static const long long MOD = 1000000007;

static const long long LINF = (ll)(1e18+99);

static const int INF = 1e9+99;



ll dp[105][110000];

int N;

ll W, w[105], v[105];





int main(void) {

  cin >> N >> W;

  rep(i, 1, N+1) cin >> w[i] >> v[i];

  

  ll w1 = w[1];

  if (w1>1000) {

    rep(i, 1, N+1) w[i] = w[i] - w1 + 1000;

  }

  

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

    for (int j=1; j<=105000; j++) {

      dp[i][j] = dp[i-1][j];

      if (j-w[i]>=0) dp[i][j] = max(dp[i][j], dp[i-1][j-w[i]]+v[i]);

    }

  }

  

  ll ans = 0;

  for (int wi=1; wi<=105000; wi++) {

    if (w1>1000 && (wi/1000)*w1+wi%1000>W) continue;

    if (w1<=1000 && wi>W) continue;

    

    ans = max(ans, dp[N][wi]);

    

  }

  

  cout << ans << endl;



    return 0;

}




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

#include <algorithm>

#include <cstring>

#include <cmath>

#include <vector>

#include <set>

#include <queue>

#include <map>

#include <string>



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

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

#define pb push_back

#define mp make_pair

#define bg begin()

#define en end()

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

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



using namespace std;



typedef long long ll;

typedef long double ld;



using P = pair<int, int>;



static const long long MOD = 1000000007;

static const long long LINF = (ll)(1e18+99);

static const int INF = 1e9+99;



int N;

ll W, w[105], v[105];

vector<ll> x[5];



int main(void) {

  cin >> N >> W;

  rep(i, 0, N) cin >> w[i] >> v[i];

  

  ll w0 = w[0];

  

  rep(i, 0, N) x[w[i]-w0].pb(v[i]);

  

  sort(all(x[0]), greater<ll>());

  sort(all(x[1]), greater<ll>());

  sort(all(x[2]), greater<ll>());

  sort(all(x[3]), greater<ll>());

  

  ll ans = 0;

  for (int A=0; A<=sz(x[0]); A++) for (int B=0; B<=sz(x[1]); B++) for (int C=0; C<=sz(x[2]); C++) for (int D=0; D<=sz(x[3]);  D++) {

    if (A*w0+B*(w0+1)+C*(w0+2)+D*(w0+3)>W) continue;

    ll sum = 0;

    for (int i=0; i<A; i++) sum += x[0][i];

    for (int i=0; i<B; i++) sum += x[1][i];

    for (int i=0; i<C; i++) sum += x[2][i];

    for (int i=0; i<D; i++) sum += x[3][i];

    ans = max(ans, sum);

  }

  

  cout << ans << endl;



    return 0;

}




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

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

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

using ll = long long;

using namespace std;

template <typename T> using vec = std::vector<T>;



int main() {

    ll N, W;

    cin >> N >> W;



    vec<ll> w(N), v(N);

    rep(i, N) cin >> w[i] >> v[i];



    vec<vec<vec<ll>>> dp(N+1, vec<vec<ll>>(N+1, vec<ll>(301, 0)));

    rep(i, N) {

        ll wp           = w[i] - w[0];

        dp[i + 1][1][wp] = max(dp[i + 1][1][wp], v[i]);

        rep(j, N) rep(k, 2*N+2) {

            dp[i + 1][j][k] = max(dp[i + 1][j][k],dp[i][j][k]);

            if (dp[i][j][k] != 0) {

                dp[i + 1][j + 1][k + wp] =

                    max(dp[i + 1][j + 1][k + wp], dp[i][j][k] + v[i]);

            }

        }

    }



    ll ans = 0;

    rep(j,N+1)rep(k,250){

        if(j*w[0]+k<=W) ans = max(ans,dp[N][j][k]);

    }

    cout << ans << '\n';

}


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

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

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

using ll = long long;

using namespace std;

template <typename T> using vec = std::vector<T>;



int main() {

    ll N, W;

    cin >> N >> W;



    vec<vec<ll>> v(4,vec<ll>(1));

    ll w0;

    cin >> w0 >> v[0][0];

    rep(i, N-1){

        ll w,val;

        cin >> w >> val;

        v[w-w0].push_back(val);

    }



    rep(i,4){

        sort(all(v[i]),greater<ll>());

        v[i].insert(v[i].begin(),0);

        for(int j=1;j<v[i].size();++j){

            v[i][j] = v[i][j]+v[i][j-1];

        }

    }



    ll ans = 0;

    rep(i,v[0].size())rep(j,v[1].size())rep(k,v[2].size())rep(l,v[3].size()){

        ll count = w0*(i+j+k+l)+j+2*k+3*l;

        if(count > W) break;

        ans = max(ans,v[0][i]+v[1][j]+v[2][k]+v[3][l]);

    }



    cout << ans << '\n';

}


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

#include <algorithm>



using namespace std;



const int MAXN = 100000 + 5;



struct process {

  string name;

  int time;

};



process Q[MAXN];

int head, tail;

int n, q, total_time = 0;



void enqueue(process x) {

  Q[tail] = x;

  tail++;

  tail %= MAXN;

}



process dequeue() {

  process x = Q[head];

  head++;

  head %= MAXN;

  return x;

}



bool isEmpty() {

  return head == tail;

}



int main() {

  cin >> n >> q;

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

    cin >> Q[i].name >> Q[i].time;

  }

  head = 0, tail = n;

  while (!isEmpty()) {

    process crt = dequeue();

    int need = min(crt.time, q);

    crt.time -= need;

    total_time += need;

    if (crt.time == 0) {

      cout << crt.name << " " << total_time << endl;

    } else {

      enqueue(crt);

    }

  }

  return 0;

}

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

#include <cstdlib>

#define MAXN 100010

int n,q;

typedef struct p{

    char name[10];

    int time;

}P;

P que[MAXN];

int head,tail,tot;







void get_input() {

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

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

        scanf("%s %d",que[i].name,&que[i].time);

    }

    tail=n;

}



void solve() {

    P item;

    while(head!=tail) {

        item=que[head];

        head=(head+1)%(n+1);

        if(item.time>q) {

            item.time-=q;

            tot+=q;

            que[tail]=item;

            tail=(tail+1)%(n+1);

        } else {

            tot+=item.time;

            printf("%s %d\n",item.name,tot);

        }

    }

}



void display_output() {

    

}



int main() {

#ifdef debug

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

#endif

    get_input();

    solve();

    display_output();

}

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

#include <cstdio>

#include <queue>

using namespace std;

typedef struct pp{

    char name[100];

    int t;

} P;

queue<P> m;

int main()

{

    int i,n,q,ans=0;

    P u;

    cin>>n>>q;

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

    {

        cin>>u.name>>u.t;

        m.push(u);

    }

    while(!m.empty())

    {

        u=m.front();

        if(q>=u.t)

        {

            ans+=u.t;

            m.pop();

            cout<<u.name<<" "<<ans<<endl;

        }

        else

        {

            ans+=q;

            u.t-=q;

            m.push(u);

            m.pop();

        }

    }

    return 0;

}

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

#include <cstdlib>

#define MAXN 100010

int n,q;

typedef struct p{

    char name[10];

    int time;

}P;

P que[MAXN];

int head,tail,tot;







void get_input() {

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

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

        scanf("%s %d",que[i].name,&que[i].time);

    }

    tail=n;

}



void solve() {

    P item;

    while(head!=tail) {

        item=que[head];

        head=(head+1)%(n+1);

        if(item.time>q) {

            item.time-=q;

            tot+=q;

            que[tail]=item;

            tail=(tail+1)%(n+1);

        } else {

            tot+=item.time;

            printf("%s %d\n",item.name,tot);

        }

    }

}



void display_output() {

    

}



int main() {

#ifdef debug

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

#endif

    get_input();

    solve();

    display_output();

}

// Fastest known solution for this problem: