#include <bits/stdc++.h>
#define F first
#define S second
#define endl '\n'
#define rep(i , a , n) for (int i=a; i<(int)(n); i++)
#define re(i , n)      for (int i=0; i<(int)(n); i++)
#define pb push_back
#define em emplace_back
#define IOS ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0)
#define trace(a) cerr << #a << " = " << a << endl

using namespace std;

typedef pair<int, int> ii;
typedef long long ll;
typedef long double ld;

const int mod=7+1e9;
const int inf=1e9+5;
const ll  INF=(ll)1e18+5;
const int N=1e5+5;    // check
int ans[N];
int main()
{
#ifdef LOCAL
freopen("input.in","r",stdin);
#endif
    IOS;
    int n,m;
    cin>>n>>m;
    priority_queue<ii,vector<ii>,greater<ii>>q;
    int cur=0;
    int pre;
    for(int i=0;i<n;++i)
    {
        pre=0;
        int t,x;
        cin>>t>>x;
        q.push({x,i});
        cur=max(cur,t);
        if((i+1)%m==0||i==n-1)
        {
            while(!q.empty())
            {
                int y=q.top().F;
                int id=q.top().S;
                q.pop();
                cur+=y-pre;
                //cout<<cur<<endl;
                vector<int>now;
                now.pb(id);
                int k=1;
                while(!q.empty()&&q.top().F==y)
                {
                    now.pb( q.top().S );
                    q.pop();
                    ++k;
                }
                pre=y;
                for(auto idx:now)ans[idx]=cur;
                cur+=(1+k/2);
            }
            cur+=pre;
        }
    }
    for(int i=0;i<n;++i)
        cout<<ans[i]<<" \n"[i==n-1];
    return 0;
}