#include<iostream>#include<algorithm>#include<vector>#include<cstdio>#include<Set>using namespace std;struct pas{    int x,t,num,time;}p[100010];set<int>s;vector<int>stu[100010];int n,m,time;int pt[10010];inline int min(int x,int y){    return x<y?x:y;}inline int max(int x,int y){    return x>y?x:y;}inline bool cp(pas x,pas y){    return x.t<y.t;}inline bool cp1(pas x,pas y){    return x.num<y.num;}int main(){    cin>>n>>m;    for(int i=1;i<=n;i++)    {        scanf("%d%d",&p[i].t,&p[i].x);        p[i].num=i;    }    sort(p+1,p+n+1,cp);    int pre=1;    while(pre<=n)    {                s.clear();        int dis=0;        for(int i=pre;i<min(pre+m,n+1);i++)        {            s.insert(p[i].x);            stu[p[i].x].push_back(i);        }                if(time<p[min(pre+m-1,n)].t)            time+=(p[min(pre+m-1,n)].t-time);        int last=0;        for(set<int>::iterator it=s.begin();it!=s.end();it++)        {                time+=(*it-last);            for(int i=0;i<stu[*it].size();i++)                p[stu[*it][i]].time=time;            time+=(1+(stu[*it].size()/2));            stu[*it].clear();            last=*it;        }        time+=*s.rbegin();        pre=min(pre+m,n+1);    }    sort(p+1,p+n+1,cp1);    for(int i=1;i<=n;i++)        printf("%d ",p[i].time);    return 0;}