import java.util.*
import kotlin.math.max

fun main() = abc177f()

@OptIn(ExperimentalStdlibApi::class)
fun abc177f() = IO_abc177f().exec {
    val (h, w) = readInt() to readInt()
    val abList = Array(h) { readInt() - 1..readInt() - 1 }

    val values = SortedMultiSet(TreeMap(sortedMapOf(0 to w.toLong())))
    val currToStart = TreeMap<Int, Int>().apply { (0 until w).forEach { x -> put(x, x) } }

    for ((index, block) in abList.withIndex()) {
        val (left, right) = block.first to block.last
        var maxRight = -1

        while (true) {
            val (curr, start) = currToStart.ceilingEntry(left) ?: break
            if (right + 1 < curr) break
            maxRight = max(maxRight, start)
            values.remove(curr - start)
            currToStart.remove(curr)
        }

        if (maxRight != -1 && right + 1 < w) {
            values.add(right + 1 - maxRight)
            currToStart[right + 1] = maxRight
        }

        val answer = values.min()?.let { it + index + 1 } ?: -1

        println(answer)
    }
}

@Suppress("unused", "MemberVisibilityCanBePrivate")
private abstract class AbstractMultiSet<K>(protected open val map: MutableMap<K, Long>) {
    fun add(k: K, v: Long = 1) = map.inc(k, v)
    fun remove(k: K, v: Long = 1) = map.dec(k, v)
    fun removeAll(k: K) = map.remove(k)
    fun clear() = map.clear()
    fun contains(k: K) = map.contains(k)
    fun count(k: K) = map[k] ?: 0
    fun isEmpty() = map.isEmpty()
    fun isNotEmpty() = !isEmpty()

    protected fun <K> MutableMap<K, Long>.inc(k: K, v: Long) = merge(k, v, Long::plus)
    protected fun <K> MutableMap<K, Long>.dec(k: K, v: Long) =
        if ((this[k] ?: 0) <= v) remove(k) else merge(k, v, Long::minus)

    abstract override fun toString(): String
    abstract override fun hashCode(): Int
    abstract override fun equals(other: Any?): Boolean
}

@Suppress("unused")
private class SortedMultiSet<K : Comparable<K>>(override val map: TreeMap<K, Long> = TreeMap()) :
    AbstractMultiSet<K>(map) {
    fun min() = if (map.isNotEmpty()) map.firstKey() else null
    fun max() = if (map.isNotEmpty()) map.lastKey() else null
    fun ceiling(key: K): K? = map.ceilingKey(key)
    fun higher(key: K): K? = map.higherKey(key)
    fun floor(key: K): K? = map.floorKey(key)
    fun lower(key: K): K? = map.lowerKey(key)

    override fun hashCode() = map.hashCode()
    override fun toString() = "SortedMultiSet(map=$map)"
    override fun equals(other: Any?): Boolean {
        if (this === other) return true
        if (javaClass != other?.javaClass) return false
        other as SortedMultiSet<*>
        return map == other.map
    }
}

// region kokokara template dayo (^o^)
@Suppress("unused", "ClassName", "SpellCheckingInspection", "ConvertToStringTemplate", "MemberVisibilityCanBePrivate")
private class IO_abc177f(private val separator: String = System.lineSeparator()) {
    private val input = System.`in`
    private val buffer = ByteArray(1024)
    private var pointer = 0
    private var bufferLength = 0
    private val sb = StringBuilder()
    private fun Byte.isPrintable() = this in 33..126
    private fun Byte.isNumeric() = this in '0'.toByte()..'9'.toByte()
    private fun Byte.toNumVal() = if (this.isNumeric()) this - '0'.toByte() else error("$this is not numeric")

    private fun hasNextByte(): Boolean {
        return if (pointer < bufferLength) true else {
            pointer = 0
            bufferLength = input.read(buffer)
            bufferLength > 0
        }
    }

    private fun readByte(): Byte = if (hasNextByte()) buffer[pointer++] else -1
    private fun skipUnprintable() = run { while (hasNextByte() && !buffer[pointer].isPrintable()) pointer++ }
    private fun hasNext(): Boolean = run { skipUnprintable() }.run { hasNextByte() }
    private fun hasNextOrError() = if (!hasNext()) error("has no next element.") else Unit

    fun readString(): String {
        hasNextOrError()
        val sb = StringBuilder()
        var b = readByte()
        while (b.isPrintable()) {
            sb.appendCodePoint(b.toInt())
            b = readByte()
        }
        return sb.toString()
    }

    fun readLong(): Long {
        hasNextOrError()
        var n = 0L
        var negative = false
        var b = readByte()
        if (b == '-'.toByte()) {
            negative = true
            b = readByte()
        }
        if (!b.isNumeric()) error("$b is not numeric.")
        while (true) {
            when {
                b.isNumeric() -> n = n * 10 + b.toNumVal()
                b.toInt() == -1 || !b.isPrintable() -> return if (negative) -n else n
                else -> error("failed to parse. [n=$n, b=$b]")
            }
            b = readByte()
        }
    }

    fun readInt() = readLong()
        .let { if (it in Int.MIN_VALUE..Int.MAX_VALUE) it.toInt() else error("$it is not in range of Int.") }

    fun readDouble(): Double {
        var n = 0.0
        var div = 1.0
        var negative = false
        var b = readByte()
        if (b == '-'.toByte()) {
            negative = true
            b = readByte()
        }
        do n = n * 10 + b.toNumVal()
        while (run { b = readByte() }.run { b.isNumeric() })
        if (b == '.'.toByte()) {
            while (run { b = readByte() }.run { b.isNumeric() })
                n += b.toNumVal() / (run { div *= 10 }.run { div })
        }
        return if (negative) -n else n
    }

    fun println(): Unit = run { sb.append(separator) }
    fun print(any: Any): Unit = run { sb.append(any) }
    fun println(any: Any): Unit = run { sb.append(any.toString() + separator) }
    fun flush() = run { kotlin.io.println(sb); sb.clear() }

    fun exec(action: IO_abc177f.() -> Unit) {
        var t: Throwable? = null
        Thread(null, { action() }, "solve", 128 * 1024 * 1024)
            .apply { setUncaughtExceptionHandler { _, t1 -> t = t1 } }
            .apply { start() }.join()
        t?.let { throw it }
        kotlin.io.print(sb)
    }

    fun readLine(): Nothing = error("readLine is disabled.")
}
// endregion kokomade template dayo (^o^)


Measured memory_bytes: 86548