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

public class SegmentTree
{
    public int N { get; private set; }
    public int[] Node;
    public int[] LeftIndex;
    public int InvalidVal { get; private set; }

    public SegmentTree(int[] a, int invVal)
    {
        InvalidVal = invVal;
        for (N = 1; N < a.Length; N *= 2) ;
        Node = new int[2 * N - 1];
        LeftIndex = new int[2 * N - 1];
        for (int i = 0; i < Node.Length; i++)
        {
            Node[i] = InvalidVal;
        }
        for (int i = 0; i < a.Length; i++)
        {
            Node[N + i - 1] = a[i];
            LeftIndex[N + i - 1] = i;
        }
        for (int i = N - 2; i >= 0; i--)
        {
            var iv = Marge(Node[2 * i + 1], Node[2 * i + 2], LeftIndex[2 * i + 1], LeftIndex[2 * i + 2]);
            Node[i] = iv.v;
            LeftIndex[i] = iv.i;
        }
    }

    public void Update(int x, int v)
    {
        x += (N - 1);
        Node[x] = v;

        while (x > 0)
        {
            x = (x - 1) / 2;
            var iv = Marge(Node[2 * x + 1], Node[2 * x + 2], LeftIndex[2 * x + 1], LeftIndex[2 * x + 2]);
            Node[x] = iv.v;
            LeftIndex[x] = iv.i;
        }
    }

    public (int v, int i) Get(int a, int b)
    {
        return Get(a, b, 0, 0, N);
    }

    private (int v, int i) Get(int a, int b, int k, int l, int r)
    {
        if (r <= a || b <= l)
        {
            return (InvalidVal, -1);
        }
        if (a <= l && r <= b)
        {
            return (Node[k], LeftIndex[k]);
        }

        var ll = Get(a, b, 2 * k + 1, l, (l + r) / 2);
        var rr = Get(a, b, 2 * k + 2, (l + r) / 2, r);
        return Marge(ll.v, rr.v, ll.i, rr.i);
    }

    private static (int v, int i) Marge(int leftV, int rightV, int leftI, int rightI)
    {
        if (leftV < rightV)
        {
            return (leftV, leftI);
        }
        return (rightV, rightI);
    }

    public int At(int i)
    {
        return Node[N + i - 1];
    }
}

public static class Solution
{
    public static List<int> Solve(int H, int W, int[] A, int[] B)
    {
        var st = new SegmentTree(new int[W], int.MaxValue);
        var answer = new List<int>();

        for (int i = 0; i < H; i++)
        {
            while (true)
            {
                var iv = st.Get(A[i], B[i] + 1);
                if (iv.v == int.MaxValue)
                {
                    break;
                }

                var d = B[i] + 1 - iv.i + iv.v;
                if (B[i] + 1 < W && st.At(B[i] + 1) > d)
                {
                    st.Update(B[i] + 1, d);
                }
                st.Update(iv.i, int.MaxValue);
            }
            var min = st.Get(0, W).v;
            answer.Add(min == int.MaxValue ? -1 : (min + i + 1));
        }
        return answer;
    }

    public static void Main()
    {
        var vals = Console.ReadLine().Split(' ').Select(int.Parse).ToArray();
        var H = vals[0];
        var W = vals[1];
        var A = new int[H];
        var B = new int[H];
        for (int i = 0; i < H; i++)
        {
            vals = Console.ReadLine().Split(' ').Select(x => int.Parse(x) - 1).ToArray();
            A[i] = vals[0];
            B[i] = vals[1];
        }
        var answer = Solve(H, W, A, B);
        Console.WriteLine(string.Join(Environment.NewLine, answer));
    }
}

Measured memory_bytes: 56376