Scanf.scanf "%d %d" (fun h w ->
    let ab = Array.init h (fun _ -> Scanf.scanf " %d %d" (fun a b -> a - 1, b - 1)) in

    let best = Array.make h max_int in

    for x = w - 1 downto 0 do
        let rec loop i curx =
            if i = h then () else
                let a, b = ab.(i) in
                if curx < a || curx > b then (
                    best.(i) <- min best.(i) (curx - x);
                    loop (i + 1) curx
                ) else if b + 1 < w then (
                    best.(i) <- min best.(i) (b + 1 - x);
                    loop (i + 1) (b + 1)
                )
        in
        loop 0 x
    done;
    Array.iteri (fun i v ->
        Printf.printf "%d\n" @@ if v = max_int then -1 else v + i + 1;
    )
    best
)