using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace SolW
{
    class Program
    {
        ///////////////////// TestOutput
        static bool TESTPROGRAMM = false;
        static void cwl(string s, params object[] args)
        {
            if (TESTPROGRAMM)
                if (args == null) Console.WriteLine(s);
                else Console.WriteLine(string.Format(s, args));
        }
        static void cw(string s, params object[] args)
        {
            if (TESTPROGRAMM)
                if (args == null) Console.Write(s);
                else Console.Write(string.Format(s, args));
        }
        ///////////////////// Vars
        static Worker[] w;
        static int[] workerStatus;
        static Level [] poh;
        static int n, m;
        static Dictionary<int, List<int>> jdut;
        static Lift l;

        ///////////////////// Structs

        struct Worker
        {
            private int time;
            private int etaj;
            private int outtime;
            private bool jdet;

            public Worker(int t, int h)
            {
                time = t;
                etaj = h - 1;
                outtime = 0;
                jdet = false;
            }

            public int t
            {
                get { return time; }
                set { time = value; }
            }
            public int h
            {
                get { return etaj; }
                set { etaj = value; }
            }
            public int outt
            {
                get { return outtime; }
                set { outtime = value; }
            }
            public bool stand
            {
                get { return jdet; }
                set { jdet = value; }
            }
        }

        struct Level
        {
            private int people;

            public Level(int p)
            {
                people = p;
            }

            public int p
            {
                get { return people; }
                set { people = value; }
            }
        }

        struct Lift
        {
            private int etaj;
            private bool PeopleIn;
            private List<int> WhoIn;

            public Lift(int q)
            {
                etaj = 0;
                PeopleIn = false;
                WhoIn = new List<int>();
            }

            public int h
            {
                get { return etaj; }
                set { etaj = value; }
            }

            public bool pin
            {
                get { return PeopleIn; }
                set { PeopleIn = value; }
            }

            public void addInLift(int i)
            {
                cwl("w[{0}] go in lift", i);
                WhoIn.Add(i);
                w[i].stand = false;
                //w[i].t = -1;
                poh[w[i].h].p--;
            }

            public void AllOut(int t)
            {
                if (WhoIn.Capacity == 0) return;
                foreach (int i in WhoIn)
                {
                    cwl("w[{0}] go home in {1} time", i, t);
                    w[i].outt = t;
                }
                WhoIn.Clear();
            }
        }

        ///////////////////// Methods

        static void Init()
        {
            int[] inp = Array.ConvertAll(Console.ReadLine().Split(), int.Parse);

            n = inp[0];
            m = inp[1];

            w = new Worker[n];
            for (int i = 0; i < n; i++)
            {
                inp = Array.ConvertAll(Console.ReadLine().Split(), int.Parse);
                w[i] = new Worker(inp[0], inp[1]);
            }
            workerStatus = new int[n];

            poh = new Level[m];
            for (int i = 0; i < m; i++)
            {
                poh[i] = new Level(0);
            }
        }

        static Dictionary<int, List<int>> PeopleCallLiftInTime(int t)
        {
            Dictionary<int, List<int>> res = new Dictionary<int, List<int>>();

            for (int i = 0; i < n; i++)
            {
                if (w[i].stand)
                {
                    if (!res.ContainsKey(w[i].t)) res.Add(w[i].t, new List<int>());
                    if (res[w[i].t].IndexOf(w[i].h) == -1)
                    {
                        res[w[i].t].Add(w[i].h);
                        poh[w[i].h].p++;
                        cwl("w[{0}] stand at {1} et at {2} t (now {3})", i, w[i].h, w[i].t, t);
                    }
                }
                if (w[i].t == t)
                {
                    if (!res.ContainsKey(t)) res.Add(t, new List<int>());
                    if (res[t].IndexOf(w[i].h) == -1) res[t].Add(w[i].h);
                    w[i].stand = true;
                    poh[w[i].h].p++;
                    cwl("w[{0}] stand at {1} et at {2} t", i, w[i].h, t);
                }
            }

            if (res.Count == 0) return null;
            return res;
        }

        static void cleanH()
        {
            for (int i = 0; i < m; i++)
            {
                poh[i].p = 0;
            }
        }

        static void GoInLift(int ih)
        {
            for (int i = 0; i < n; i++)
            {
                if (w[i].h == ih && w[i].stand)
                {
                    l.addInLift(i);
                }
            }
        }

        static bool WorkersCheck()
        {
            for (int i = 0; i < n; i++) if (w[i].outt == 0) return false;
            return true;
        }

        static int KudaEhat()
        {
            return jdut[jdut.Keys.ToArray<int>().Min()].ToArray().Min();
        }

        static void Main(string[] args)
        {
            Init();

            int t;
            l = new Lift(1);
            int path = 0;
            for (t = 0; ;t++ )
            {
                if (WorkersCheck())
                    break;

                jdut = null;
                cleanH();
                jdut = PeopleCallLiftInTime(t);
                if (l.h == 0)
                {
                    l.AllOut(t);
                    if (jdut == null) continue;
                    path = 0;
                    path = KudaEhat();
                }

                if (t == 3)
                {
                    t = 3;
                }

                if (poh[l.h].p > 0) GoInLift(l.h);

                if (path > l.h)
                {
                    l.h++;
                    cwl("Lift at {0} et", l.h);
                }
                if (path < l.h)
                {
                    l.h--;
                    cwl("Lift at {0} et", l.h);
                }
                if (path == l.h && path != 0) path = 0;
            }

            foreach (Worker i in w) Console.WriteLine(i.outt);


            //Console.WriteLine();
            //Console.ReadKey();
        }
    }
}