Problem:


Score : 600 points

Problem Statement

There is a grid of squares with H+1 horizontal rows and W vertical columns.

You will start at one of the squares in the top row and repeat moving one square right or down. However, for each integer i from 1 through H, you cannot move down from the A_i-th, (A_i + 1)-th, \ldots, B_i-th squares from the left in the i-th row from the top.

For each integer k from 1 through H, find the minimum number of moves needed to reach one of the squares in the (k+1)-th row from the top. (The starting square can be chosen individually for each case.) If, starting from any square in the top row, none of the squares in the (k+1)-th row can be reached, print -1 instead.

Constraints

1 \leq H,W \leq 2\times 10^5

1 \leq A_i \leq B_i \leq W

Input

Input is given from Standard Input in the following format:

H W
A_1 B_1
A_2 B_2
:
A_H B_H

Output

Print H lines. The i-th line should contain the answer for the case k=i.

Sample Input 1

4 4
2 4
1 1
2 3
2 4

Sample Output 1

1
3
6
-1

Let (i,j) denote the square at the i-th row from the top and j-th column from the left.

For k=1, we need one move such as (1,1) → (2,1).

For k=2, we need three moves such as (1,1) → (2,1) → (2,2) → (3,2).

For k=3, we need six moves such as (1,1) → (2,1) → (2,2) → (3,2) → (3,3) → (3,4) → (4,4).

For k=4, it is impossible to reach any square in the fifth row from the top.



Sample input:
4 4
2 4
1 1
2 3
2 4


Sample output:
1
3
6
-1

Submission status: Wrong Answer

Solution code:
# compiled by pythran
"""
#pythran export main2()
import numpy as np
i4 = np.int32
i8 = np.int64


def main(in_file):
    stdin = open(in_file)
    H, W = [int(x) for x in stdin.readline().split()]
    ab = [int(x) for x in stdin.read().split()]
    a = 1
    h = 0
    while h < H:
        if ab[2 * h] <= a:
            a = ab[2 * h + 1] + 1
            if a > W:
                print(-1)
                break
        h += 1
        print(a + h - 1)


def main2():
    main('/dev/stdin')
"""
import os, sys
p = os.path.dirname(__file__)
pymain = os.path.join(p, "a.out")
if len(sys.argv) == 1:
    import subprocess
    if p == "":
        pymain = "./" + pymain
    subprocess.call(pymain)
else:
    import gzip, base64, stat
    gz = b'H4sIAEc6Tl8C/+19C3xTVbb3SV8EhCY81PIQghRoBUoCBVpATWkDJ5IC0sLgAw5pmtJomtTkhNfoiLb1EmuRcRx1Ht8dxnGUO9dvLjPjOMo4PEQoIggiPkblIaKmRARlhKpIvrX23ifZ5ySBgnPv/X2/30Tpzvqf/Vprr7X2M2ffa3NMz9DpBOWTIdwgILVloJXQVoabHotHAaxE6A5/hwiDhRygs7h4VsGqCjtZ1kqoZ/EyWbqSDEqXZFhV4SAWTwl1XJgt8B+rKnyuTlCFUPN4OqxrgZeiBd7FqnA9y3RfjjpdBksXaaBopGGxKhQyBFWo8JfF/lUzvJrxpYQVLF4FFx8/cz6Wa/F7vUTpesmqCp9j8Z7TpLsZ0uUIXf8YWTiXlZdOLu9mCqpQaYexXk/NxOKx3toxXo8vtHzM8pKJYyYWFwX9ReNInYws7oxZ8+LtncHVuR/D8PlPcob/su2zQw9nv/yN+1TsruahUzLO4LNilqYb/GvONS7uWdg9A1Ou6ino8FkJ/JsK/37346kv/9L1t+097lsr/emD8W+N/kJadKBqXdPqFtdVd/70uTH/PqjxhX5P9Cxfbr/z+ULbW44LySUXCuuTArfrUuMrhNT4E1mp8dczUuPFacqdnabcUWlwX05q/OU0eL805T6XJv4N2anxK9LEn5Um//Y09Z+SJn5+mvh708h/Xpp8DqZplzvSxBfT4PVp6vP7NPWpTdPu+jT5l2amxj9Mk8+1afJ5Pk09b08T/z/T5J+XBnenqefsNHIuTFPu12nyL0oT/29p9PCjNOXWpMnnmTT1j6Rpx3Fpyj2ZRv9NafCfpCnXn6aexniPpP7cnCafs4APFa4UdjI/rqRtESgeYfgChd8MiltZv6b0D/ewfOYwPI/hMsihN8Zn+Sj9wm1MPmv7W1X1mcTaZfFANX5fNs2/nuW/SonP6il61Th2cr2FAcKRu1g9WcG1rL1ODVDnP4ThqzTlCtB/BeVa16hR2GdNFCRpSYPfJwVlZ0CWJEG6dVaVXOLxB6UaZ9BdbPd55AqLbSng1fOrZMsEQD0uiB1wOxtqQnV2F4AWV70zIMkBp0cO2l02G+a5fLnU6A4E/T6n1yOvkJaaSc7+8Y0h2eYiuc2ymCXJtXy5s8az1DIOvgc9ksvrDAYleUWjW/L46vw2TDSzSp7gQgiytoyXKqVlnlq3D557ZFIvyLUUUI8v6A7Idq/NNrfKX80YKaXVBXZSVnSCy+t2BmzwZJxkB5bhn+yU3ZC21jsH866SsWJyfcC/TPK6fUvkeskdCPgDc2YiDz5ng4AsOCWn1+t3QUrJvdzlbpQ9fh9JbJkoSX4qK6V+qaoxF7DxtKYstr1aqjZLtqqJ0pyZVeMlL+VmIhbidbP2AGASEaDFYilNpPb4lrA8UhRV5cTyyi3I8njC8uxGt6/BX+tmko7nOC7e0JBh+qws4+s8vlqpzhMIypK/zgaCaWjQVK6rWY2DVnT5fRAv5JJtDS4q/2JF/v4QliAFnL4lbqmuQYaiVmrUtWIckUytkzRetR0UgG+Qy6jUpIAbmm2p29YQb1BamxpnreRyBmUsyLesYS7IrtTnp8/kVFZUzqzIjqIPhHyyp8FNlYmparymjIvLao5JXHNAdfgmqa6+fI1RDDFRyeJl9U45SQ+7Wk0zNHXA3eh1ukCyDVjDy8sIDd/ZCCpca2OZQFtcruwmEtmBB9KKjpg4aVqqBKVxl+BfAhlzHmFWUuMyY4XqMO2gvo+r3gS+emlcKtcKSSWAYs2deRmyszHG6gJutd+6zHZwgQrJbtvcBmoqxS4w2O/RqsGgZ4kPOKsqpr7cP6HOGwrWUwMH76yxOOjVGmiHBt+WuKAQpCyCNM+3DJt1rjsYanDjQxeNVucHtRHqZLcXvCsWB95ZqnN6vAJUT/Z7hTq3v06oW+KWg4iA91d8vexe7pGFuqDbfafQ4G5wNa4Q6lxef9AtgCidtYg1+Je6hRpXQyOkwSJZ99rg9PiEGeXl0vgiszDDYZ9WvmABfC8uGqcmLRYVWSrAt7JpdslSNF6dTBWPfpfGFVkSX8cVTSBzyUz4Lwv+ZQjZ8W+IZcMcP4t870b+ZsB/3WAun8WeU6w7SYEY/Uf/YuoeLC+BPM8maTLjpWUSRJk/64QPcxLjuTkjVlwhQPr7uinPc8hYCp834r/OxyHb7kK4G8WchNYLTzA6fG9hBs6Qn2H0m/91ZzaukPyZ0XeR+FnCFkbLhY/osZZ74+VlCOdzEuO9R3/8WA6ueLzP4ocGeLqj5D5h8SN+Ou7CtQYLN5w6xeHj+NUZNn7LZvP1+LyKw6dy+E4OL+bH4xw+gc+/IYFP5PA5HD6Jn7dx+BQOV8aTiF/Pz3saKd6NG+OS8TSHZ3B4AYdncriZw7M4vITD+XUtK4fz6zoih3fj+eVwPYcv4PDuHL6Yw3vw8uHwKzi8kcN7cvhyDu/F4as4PJfDV3O4gcPXcriRX0fh8N4cvo7D+fnPeg7vy+EbOLwfh7/A4Vdy+BYOL+X1k8Ov4vB9HH41h7/L4Xm8vnF4f17POXwAb18cPpDDOzl8ED+/uSuBX8OvN3D4YH5+yeFDeP3ncH7+aeLwobz+c/i1vP5z+DBe/zk8n9d/Dh/O6z+Hj+D1n8NH8vrP4QW8/nN4Ia//HH4dr/8cfgOv/xw+itd/Dh/N6z+Hj+H1n8OLeP3n8LG8/nO4mdd/Dp/M6z+Hj+f1n8Nv5OXc9JlebM3e8wOTILZskTNi+8SmV/TbhNiE/QDFhh+Av4YhVviGdD0m6TgSg8/wXUijq+zYR+iXkUYX2bGF0BuRRtfYsYHQf0QaXWLHOkL/Dml0hR1rCf0k0ugCO1YR+udIY3U7Ggn9CNLo8joWE/pBpNHVdcwh9P1Io4vrsBJ6JdLo2jrMhA4gjS6tw0ToO5BGV9ZhJHQN0ujCOgRC34o0uq6OU+eRnou0kfBP6JuQ7k34J/Q0pPsQ/gk9Gem+hH9Cj0O6H+Gf0NchfSXhn9DXIn0V4Z/QA5C+mvBP6D5I5xH+Cd0D6f6Ef0JnID2A8E/ob+YDPZDwT+gvkR5E+Cf0caSvIfwT+ijSgwn/hH4P6SGE/++Q3o+0ifBP6F1IDyX8E/plpK8l/BN6I9LDCP+E/iPS+YR/Qv8O6eGEf0I/ifQIwj+hf470SMI/oR9BuoDwT+gHkS4k/BP6fqSvI/wTeiXSowj/hA4gPZrwT+g7kB5D+Cd0DdJFhH9C34r0WML/OdL+SJsJ/4S+CWkL4Z/Q05AeR/gn9GSkxxP+CT0O6WLCP9BzNn8RWCxE3gJRb8Y1q01IbtwJVhr5MRS/YFtdkWFIMzFRw5AKGIOdsIffWCSGj4pNx07Nqba3bzFWWQWxfeu6uRi0bxgENnrl+SqT8A8S/7QqA6vwwj7IWrwe/8p9XyCWD+befTMCsSN1a7eRVIk0m0j8+z4nwdbzmWL4lLg1cqOo2yG+cV7uHc+hG8tBm37V9SuAXyF09Twx/HHkRyCAHdlLANEtpDG18aNr1PUtm181Rwx/tCkfuQwfjowGTcQQY4itg/LFlvflArGp3BQLDRVbp4ht5UaxtF3OjrhAuBjxNgzbs0hfY9mCTu22skXb7OEdF0w9nKW+hkvtCJ+NnIA24SsozCv7Qdn8snll1VXifZ+9C27NHj4vtt2dX7Bp1gKrELkHDElsr8gnTndHRX69sBlVZxMOkyNoPyi7AjG8VWzaahTDerHdSkZzO6xGSGc1oV+FkPRk0Qyo/4sx+rlXDFfkN4phR/5ysb05X1kudbR68wsc4Wfz1wJR2XJCzrY32Uw6e2uOGG7Of4I1VrbYBFlzNZnPanKjGN4uNm2BmtiETaTs8MmN6EsjT32LgrCxCtlIhUQoZx0tJ5TX4eqN2slhhuY5ANlbFwoVD07ZnBcvrOMcKczQ/AuSx3axLagrWxWbJxpsp8W2l/L3YXkV12DSHBKve29s61+SB9BihuZOIwIlYuv4yCCsF9SWNuJwVSMu/oY24gIMQUj7lL6u3aZnfJChJ+a9ivGzipYR6h+dAswkP5DzoSR9LHQNltQSg1IGsFK+/BrCViUicP9NJnar94CaNPeAcnY056/GSYXY+hJpHUhtaC6CB5vGgm6/iD2mZX/kJcytqRMerQGAa6I/fRtXlm20iTLF9nKqLOWoLOWsbcoVZXlfbL1HiMzsjMVQ29tACVFnFhMtFEFPQHtuhz+gJENFUJJYaAAmENtsTHxDkaHwyUh/CB1hOX+5ncQaZodY9nisbzvx6cnI6U4UckU+KX3VS4RX4LzOgPLlOJ5q0HC862uFY6dBxfHWby7dPIBBPWr6etKszawxQIcaoDRH23NEBxxgnyWGIato2xvBrjfhHC2y9mummIfUoi/5huFfGojC2uH/pu2QrgBdwuSzKKZtWHSJIxwRm741BgaA3Bzh88Dd7q+ZfrY68kvEcKWRuZxvdaF+hucfIvVZrY9epbgUMdzuCJ8Rw+9FAphvawWmssHQrFLYkaUTkkyw9W5gGOU6nwg6BP/m6SMPnEGZYmtdhW3qKD0JLXXzWdqedpIxJ5ubdcScIo3QhEC33EpoB2b8qqG5tRdSoLZ2kOwuces3N4pDd4m6XYbnbzfGOCn1odKTx3A+xLDpTcWNRGrOJnsQaLMTm3qAo3SEY5Gb+zPDac3FEm8HztHY7yHUPL04pUofMokt++WJYPhEt/eewQqXGR59hZp/z6jZZjlGvssjCP+yaGs+Jtd0/BsUVvacjkb7OOHB16ocxtgz1JRHnqG6XEJHxijHF9S2kX2GyvK7r2IxKCF0HS/QlmfAnW4eBzq+aSIqenm1Vdh4C3q1RRCd9A4iqCLqaMSBTEMrF5CW2HAFlmfNA2kXoEIZxdYF+s0FcRn//izTxHUQ0fCDLYbeqP7UibVDMiLqivw8tA1yiiF8UiyMiuGD4tbvoOuOQNd9vaHF1JP50dU62pku+Yr6iFZMCn6V+LVrsa6gBXmOsMURvktvb8v6XAyXoQIb1szSYX8YoynaRCN2RAug1YnxbcFqbI1mik3bdNGJ6v7cEQYxNm2HeDvFcAF6hp1Exu16iB1DuzCs+YKwQZ9ERg1HNtrF1odovq2FWOgCcUpB6E+swgIWiiMRsRBs83M7DlNaTjjCp14kAjFUbJ3Vlm+Od51D7KW7HYYZHzp0pxyGaR9WthyT+9zUNvVjMh2//R8oiu3RTJvlxE1tWV+RTlUXwRI24DZ3+O6vUEkdrc+REuVcB1o6GOzxyH1f0Q5gA2Fou76y5YysRw/x7mlqySBJaNV6/U1toz+m+Z4gvHR8eR4jeKG5m2x5MfkqGpThQ7DBLaFAB+kqoSd1tIb0jtLThpa7M2h3pMf2W3ZaSQ8qecdpYvt5sdBmVYoH+RQ2kuLufGNkymnObyslykU4QoiFRqI2oC0TpTeyRPpIzmnao65XelTUE8VJFG4Vt34Njf+1zvDAUj3fGfyhu6YzGEsAq15pQFXH8IfTSsewrrvGm/8KhxDgsTadRgcgj1Zl+h6UuemOBYmM6uMZHdTx1VmpzVZk2V79BXXpYKmLN5JMzkS2jVR1a9qkvVjSD05h0u0kqRg+BKU/OBIV86DYdo8u8vopZmhcyjexY2/VEz8J2oKa9PiXpHzOuf75NDP8T4ltbMVGsYf3imGdGGYDI+x3hotKFxf+DswTSnecVvof2tewLsjQPEhH0ugMLdCtCGUP5q7Wd+CoSDPfQI3KQ3G0Z1JnuE1vLz0k3ym2jsKRw0nqHSO8d9wd+RTYjG6Pp3/3VFL6sgumf4akt1liHT9jSgmOMA+r3dILXCuZqKnQQkRHo9dNiOz+L2l/1NDF4cOMRNd79iTtIfcRFzpDb281YOdrb59BkkBYQCcEd+eb8Q8ZB/wRK92TjkHM+KcAlaBEbJPzCyLuvpSPEtKIr2bH3XwexjSJrfW8m2//grX2i9kXcvP6hJs/jBoWjopbv80UX1D8nFi6zfBvrTmsV63T0dZYeTLu7PVxZz/hJHX2+oSzP0Sd/QnDmtEJZ69P4+xPgL1v10UL19rDg/LtMMkC/+4Im9T+fTtY4Xfg3z/g/ftMMqHbpvh3R+tQ4hMdU0zUv+uZf0evai98pTL8qX1rLBOctiPcyfn30SW8f98D/r3DoesE/96BsyD07yeIf7/7c8I9+vczM9uyzpNedmZ40HnMEWq7gTn1szB8c4SPRp4lgrkdXfM28Ogx9OixSM7nVAGBgKZeoJ/dlv85deXdYtQVm5JduZm68ie0rvwrHeeYnz2hpIem+tWJ1K48xqdYeYJ6ZVOk8QQ/bGElyqOoK89XuXIbS2SOTDnB+f+yzShRy/v2TfFpZnzCWfYSkXZrNXr6DLF0mt7QjHtN4pQ8Q9tg1rn0gV7Xsl88exr8LbR0O8D2thkxTAUNOU5sXQn9w1kRWlAs7TQ0/QCezyqtPd95rz1F6jCmLo0ZmswYrTX/fFy177WXvmJoHodj+ilPkZ7D0NYLqgeap3O0eWKVpR8bHupLku82NA8jtSgetBk3fSK3foasZ79ZYcKuBzzP+n2BxdREMMWqe0oEubvheVt5dADM77EZniApbPh9E06GY3PMhk2naG49o9hE23T2pvYMcCCRh6I4HeroOABdOo53iP+Lav2fofkxIkviA6PUBx7jfeDOyG8gUXTrWlJ+Unq58YL+cwmm3U4qKLbvQIFFaqOE64PlCtdPUK5xNo1c/xC4tjxYXh6dhopjUhyrBx2rl7nbONqC6Orv6GB5JckZRpeHk4RzsgOjtEeWHWfmgk4vJufScRt+D02NDos7oQ3HlfHF0ywBi3R1PEobi5IXaTpOh9KLIz+7EuRy3yu4+HJb2e1lC8sWlUkLt21eAyOATf+BwwD9LTD+PgfqETkEFdr8ya3wIHgbPHgL/mzEpdfIdnxw1e3w4En482LWQniAa7CRZ+FBpB3K2ixDLpvKIe2Lv4U/G3GFNbKmQzXQf3U+PMClnkhI/SA6T3lwOz5ATx7p04GeqF1sezb/CFtjIB00DKveZcOqHc3kkbIQ0nI18MDl+l9VSq458VxfitDxB0j918DApgIJ4qy1U0UcElWi/TQR7fhAiLZ2ERetE9l9GHiJ/CiiJKhNJLAn5UvkQ6Jdn4j2SFK+6+L5jojn2zOR4Isrtfn64/l+/Gk82q6kaCJRikbQrh394gtIf0Ldi/sLcRSVKjiWPssMm0/CjCzya8gz8hmWz9Js+gUKFJfqIzZ4RqUe6s9JPGueMpN7FCvUahZb5+jjRRo/VQ1AdMdJL45TcBpBJNPwXRDL8n50CbeOo4zNSjtC3Q1GmDb3FqIGMXwFjkGobsAMtZVxEC7XX0hXtAtB9vZuR6AR4jwScY7A2qPt/56YNrqSUIEy4iH+oW1qlnhfO5Ktz2WdgqDpdV1kLwgrOhBFbvskITYxDPPClyM1mGebN18Uw14Y50CXYmWLniL0XM35uJ1eCeLoh2NUrCIZHkVGQU7RqVj2KVL2Q/mdWOvSLUv72gt3kjiWMzCQ3QbZR/uJHGQPb4n8X7XI10SoyPuhjyih8r4VCoDOPjoPBz1k2JxDF2N4afe0h4lXEu3h6Ub8YoUv+hSc2NunszHgdDZjyr6r1ERGKFR2vVaWMhcbfiiLb6TlDYvJ5Iey3pxvxpB0xi98TGdTGGsBsIGCxXOukXuZlK1IvHwMWE2MEX/zKWU1y3IiOhNMQz1M3Izj3MjDmDGMfsn6KA7XbEYY3+G8NNveBHyQlaV2Wx5bkmFjST+ZuZowRizU3956g71tOhs25H6MvdvZSA6EoFgvgGIlTBwHRn/7BJ3aK6Q7Ig77A6g1qTBqzWwg0ub9x2M079+RMBZ5ErKy/lnX8RSp1CuWEx0/p9/ibdsj8iOIG80kWPbxSapmOD3pUpvBcixNM3Qe45phykesSKzj+Y9JHXHsci9ddhpobT4RCuLC8Tq2Wt2yB/d6csiaGrfWtO0j2n3+FUJII++OXh/NimZECYcgKxfgHZkweI8jNyPSL4fJgHcpyz6iIhuLeSaKDs3veJiKrOMgTCQ6HswmRLw5thylEu/EjJ/AGEYYCnQ8namO9rOjqlzlG+gq2iQVO/84Stn57CgV4jrmlqJGPqtZR+kSCd2IOCGPocOXEerFtfVH6eLaOpbXE/FVhmfZLD9dSh9LWcdSro2n/GV8Ab+ALuAPjS/g38KqbmGJVsUTeeny+HW0rGHqsjJYWd98SAfQeHqLbnusxG0gTGJo8eNX1Xr5ax/S9fJtH3Ljbkf408gjH1HTaYJRuWBoOQoK05GZRVsbMD1gD0PLdPQBrGMzbaOOo5q2OnEEh6M0thNjH9NE2A0ROmZksmxJHfGnJ4lV4lEfUraGQdgxmEVMjN3G0IEg+W5PfDc0/4n0rrTuI7DuMzKV9SRl8LbviDK+23FEGVGS8d1f2OiywAG9uKP0K3kaTnfSbs6tPkIbbNURsqLMzi9sh4Hx56EdSlbYcHpk5NYjyvxojqpUQ0tlLD6u7WLJuazknC6VfOSwUvLbh1ULykRKzSMylFkaTtAMLVfFaX6m9ovDykztx4c5jemI6OJNk8c1jZFrGqOmaVApHNg0e3W0pMRi74TDyrh61GFlbSXRNMYuC+jEISqgjw+lEZCRF9DmQ8oq5J8P8aUmmqbrJQdZyXd2qWRbvOQph/j1TyKl0HUd/5d1NRD/Gm4jhVm/oeWtc2Adb51LTGsgxt1xbY833qGDisYfOKheMY3OUtlVaJDaVH4bT/iLg2mmQvcfVJps+UFlKrRGT33JdGjEOrL+ltiebvoMXPFZe/g8N15adJiukS2CwWhiV6sSV1FbiVuKRW77gLolst7U1GlYOhhXtHDlAQZlnx8iq+VkDEt23sqNuJw+1N50ThfqVfZgt7LVNiHaB4a7RWSdnCyp/OwDRWw4lG29gu5raUat4cFi0yvG+Hxu2+beuJ1+A6nMDubNDkfOv097sPmHFH7n8QzXi+HT9vA5Mfzppu6Y/CRMyh2to4iTrsCOtOkesInmvxJnPzqfrAHYcpR9tEo91BmYfPWgsnz8W4F24iifa0hHvMPReqMSW2x/mUy1PQe1q7dnD7L1vEcIa9srdecdum/pYNQmOApP4woC7sbqySruICJhWvhDB5Fjun+ot7P9w3qyf1hNFm2jt5Edflb/0MSOR9Sblz+kZcsD7HRbDjOzt9vIOmjZDptRiI6yWU5QHb81OjGxCPrle6yZIIXezvYf7WwDz67sP5J016p7xsh7tAs58l7i8AQ3cu34gEnjWdK7tadZ4GRrm45wbb61Mjw1n7TaGkhS2bZMb2+bYSQ7rjbLMUeYnHm4O38O7lKL0aLEEnbdWjG8kLgBR/gULuOZxXCBPfwB2vniGN2i39QT1wiySFEnUT9L3ydzTYKjWekjfzlHFwH1ZM40LAu1YLzYOhPbCNfrnyEpiCcvp+LgHNN7f6eOaf/fqaPR0xl9JVkiLTxiuB9/+4wzjcWOwo/FNtxICWNbo7MrjYiG6RH0Qt1J0VtJVGjpNuIQvjMGriE1FMOfgK4sZtUAo+qZj5nkYcpRDt1HuO4a6vfgFaAug9T7cdDeYvgQMpGB9WvNymf7jlAFbHBOkyzvU00azc9ccZe4DZcES9+Qx5MpK9YM/EB0FF3/JxvUpLpEGrvfJbPfyfE6GDOw8Yl/JjNbXCgEKRnZjCsvyTUQ7/Q2Lum1FtEl9SkFhpZ+YNqVYIvhiKOwE+ySbgJu4TcBb2rrx20CiqW7RMOMNxy6U6Jh2htiy34seoG8DGa+b5GV4rnvEsc3MzzoH2K4w1H4tXyH2LS1M7xzaySzaYtObDrSTW607LecUZ0HsrdOfccennrA3p71DjWQHZ1i08s6sXRf6CPQLrHwS0dboNMR7hQLT4lNX5cEp3ZgRNDjREmhxyqJj0WFRXZb+mOvPYgswx/FpJDOcD8Zjze9DNy+naiC2Ar2OgtEyCgRSaOy8QE0OIBZeXFjaxXzgDah0THaBHSBYnxAg7nMMiubJECbgYY5sdXM6BKgrUCToY29aYcVVMMKimtouQvEXBn+LjpcbY+HIzvfxtkj7aLtaJulJ+SRdta5f05t6FPOhl6LPAYpoq+gvkIJRnLISREOXZAPvY2eHVxAZXhkZXiZnizG29tGky62xNEq47IEZ/ktOWDS9DzLAPX4fNTbdHw+7G30+q/Uc0uKNktM5Y1aAt+qVvkS63FL31I9SCwbLcQHpCsL4rfH4cGmKeT8w1HLlsh/vZ1mOXEERI7epfR8WL2st9gJD5gVCHT8nnDAS96iDlh6S316bew7dOsHxDySitmkPv/wFjv/gMVl48RzB9qvNfK8TjmlQEY6JvqdH+n84wAdjRREjh+gffLLwEzdWjy/h0fiWiUrFtuNzpLH21sX4ekOuZpWo1JVjfUHaDXWHUA9mU40K3qdKkoLi3IPjWKlPpXkGXoWvpi5wsYCbUJ6Dp352eMzP4nlMonmYkpR0CAWpR+NYmYFYX6hDfDFyBWkV04Xqv3/m8z/v0lyoHbHItatrRLD34psia6pXR9xCPRIxlO0KW7r+MWb/InDpPiDWHxZiX+nOn58OAQDFbSWH9qbZsAwUoY2sbcOqWz1g/VFQ0OjM9h5KBw9Fryp2W84KA93tA7Dkd1JexNMcsA8wc/l29vQawOTuyJf7QeN2QY5xrelPtpP1yTe349sk5+0JEZziQqS+pHDk0/o6OFJZb0S5k10sXLFfjq8NW16He0IOSbliW24LRcelB/vVXdgv+EA3ZxTCf0U0VIrdlEiLieacDkx/ClZTFwKHEaH4jCrEaDIM28A2UeMP8eVxao3VSuLxQdo55dP5s04jIKeErvZ0r/Lw+xh+IJdmB37zmh/EYQjlh6Gxj/4Bi4+HosWG4yZrJ/T2+khNW297UCxsVX8NEb2lcNNAtsh7jV0uLKi5cgykSkLXcu6G5hoYwcKiMbVv8GmNHQVCycGE/bTJSxcEIks36daSbzlTcrafOjXU60i2t9gq4iZdBGxHOYIQ1EZcogy6Ei/3V7ORm3lbBVxkR6ihHpFiyzvMwLkRJVnoEp5siMv7ENV+TSyYR9RlTmSFfdzUB9QY1BfyAEgZrQP7ouvKB6OfLcXVxSPGZrXkb4Esze0PEpsVFXEPFZEJYTRZSQ72kQ9IpP30QU9gLKfHpYQ9x+HdVHcX+9NEveOfZy4u+9lBaBX3P0GNYun3qD7g0n2f47Z8W9IhKTno9nB5OY3WLwf7lXZO5n/oDmtJy67GzbsLcQB55GTCJCGHujti1UsvT2/QM4FYa8nwia9HJqVGXfziPGdex2k/SvsiAqZp1m5N+XWSKLzW/E6dgW4UxgawtYz2IZCU7u5Vc6ag1sJzSj1PMzvmz3UvM1kHPpyZADkDwahH0lBHAhtRNWK6PYqu0Hv7CEzLDzHmYcDf82IET3A4vhWA2koMozfAslghoP+Ab3CAn6TQU/8wqK93CaDXnEF4l66ysvmvZHlQFtObMKfHG7E914g9spedqoC0jlKY/LgyFEs7Woey468vocu9vbCJPftoXoBEbLHDKWKB7LqVTo0oXhmsmqkrFlTVuiyJtW9e/awhSVF9xojN71OdQ8tItK2m3bGE/aiNlV0yd9236P42zkwMtmIPy2JtOz5Xv4253WVv520O9nffrRH5W9fef2y/G3D7u/nb387JOEA/jCkiw6g87UkB7B9N+cA9K+p/G3Hngv727+/9t/sb8XXqDO0vkb8Le7iXMDfDniN87dtu7rmbz/eRYs4uCvJ3+7alfC3EwcnxD1tcBfFHd6VJO75r3Hi/tmrnL+9fTf1t8W7qb/F8eiqewsEebDY9E1msFhsnWHCxphLRrNkVNaxepfiaHyvsrPd7ZGqsyAG3HaODqDP5iaezRDUW92HI39+Lc0J4NuxcmRgDbHufZVa5+OvYeVWdXE85HlVsc8GtE8T2R9/9XvZZ90ulX0+vjPZPst3qewz/7XLss89O7+ffWYPSihM70FdVJgFO5MUZvirnMLUt6vs077rwvZZuvO/2T7Xt1PjWdfeFftc2c7Z54kdXbNPGyvi+vYk+7yuPWGfjw1IiPvJAV0Ud8eOJHE/386J++vtnH2+tJPa56M7mX2C/tvD7+CUxdE2fGl/kzBPbBvzIwirysLf2cNncJEMf6u69bvMyIzt2FInZJPlfWUA5Ah/4wifqQifLIv1+4Asq5YeDB0nlr0wPv1Ymxgwnd7GfvtKfu1K348wtta9dGxQrvX4hMAofK+FMLbe3+Ae6/Pc4Rnb4PF5XH5frXP8WLdvaXCsU3b5a90BfD/i2MYVcr3fN76oZGzQI7vHNDpddzqXuIMEDzh97LnHNTYke7zBscF6Z8BdKwXcdUX1jY1CuT/krfWNlE34ig5TncfrNgnVpusKnD6/b0WDPxQ0+ZwN7iDk6i6cPFnJa/JkktnkyYncpkLdJ09mbx+ZPJl/+8hUfPHIDaYbJk+GQgJO2R8Yc0NBoYm8f8h0W7XpetPF0i6EOo24jDpdNAm+6wqSSMg4V7/r1NW7pGwWCnz9J0+m78y5TAYuRajXXapMhwcnmySp0R80FSyr97jqTZ6gafjKUKHpBpNc7wmOuSHoWemGTNVPBfvY2SZapsfvM8H/5IUstUR5vo/uLHW7gIupXr9vyWhae/aqLwYCsxfVoS7ksVCgkSZPZu+bEjy+pU6vp9bkBfsJOL2mOn/AhJEh/2Ueud6E75UyWcyTR/4TuOuqKkFLJTFwCWkvQVb/czVaKJh6wP+9umsshH8XmckX8npNPr9sIm2iiRkM1cBXYTq6KYxDnRY0F74MCGIIAaeAaliELwwCliebTHbWuM7AklCD2ycXCWbT1OtNPtOIEfBnqqnWKTsVTf+nu1zCPiQJysTZIolyMiEytfoGVME6d8Dtc7m77GNIUqLKiea9bWEBIoW0cfHrQqGgoMZ0/fUms+nuuyFv03WmGtMNSALbtBFrggXOQhQFIX0gnABI2utp8MjBqbVulxcLLKgphHIanMtBmGMTCWsKC7l8p6bI94Yu5evxJeULOUNW1/qXugN1Xv8yk6ve7brz2n96yyiik8Y2hLykcVBsF2+FeDqofchbQB0NET5IHGWOQi403YiyuQTZjjHVoLYWdFVmY6jYnf8L8nLW1l6evCBhCnlNvRxxjbpEcY363xMXuKzLExckVIkL33NsGSfNcMyeVuaQpFmSpURJN4H4hkn22TZ8SZ3tIvEsE22+pZ6A34fusGspxlfJTpBIoLZL0UttyhvuLp7xNOhbuejsfUPsPVzfLrSq3r+l4G8w3LzIqsKfZLiowRsZvliDiwxfvkj93ta1jMaJNQltLL3m/a5mTbwtmngXYd483+kNuZlI+Xp1LlLXN/7eI0ld3ga7ujzdwMwpz7F3TO18IRbDg6QFL8Vi+F7lBRCS331DeA55/1ssNgfwCISrIFz9QSx2AEI81zMoUxD0H8diJZj+k1jMC+ECCPGnu6shfArxT2OxRohXcDwWO4LLvhDizx2WQ/gc4Pj7lX9geBLyyRKEklOxGL6Bp+R0LLYBwvUQdrKXlCnvytKtnCvolht1A3t206/VdTMa2fumVv01FlPee5Q6Ln2fF8ZthrjKu9Ly2XuLNvwlFluMW0u5xum5eTcZrlimXyXcOGDKdePzyeujzOwdxTs/isUG4wx6Wq6xLDevLNfUlLkmI+MEfjVOy9UD4Fa+49b1Q/gO82OxGHl3FMBNGVKunr2DC89c7UzxDDcWX4F/eEaZXHcwDbPLm5ZrmpZbUJZrbsp5KLsta03mwxkZzbkFBM4jUfTs3V5QP2skFrsmnu8P4mXiZn1FJLlMlBm2pX5jLDaUPcMn8XsPVs5xEGl2y8RXG2cqMh3NZHgK0v0E3ym3vNaqkc1sTjbCHLx7APUR2uDngyH+aohfxvE3LddcllsyI3dtj6ZuD+W0Za/JejjzgYzMe3rnlgDr0zh+yzDHtT3o3QUoy2f/Hosdxzq85LZqZVaRa+XE9gcsRCW5slwrqRse9q9+LxZb0w3yOeBOVbeK3HU6Vd3Kc1LXbZ2O3gZRAeEG0Jtz+AZEYx1XN6jEjNwtmU3ZD5F6ZRozsLJ8rbZk0vcSol29BHY1EPMw13H1InnsgzxobXxcDqQW+zKxDjsh/S8jrA4LLr0O2M490UdEY7GfkXau07Tz7Uoz26CZSZtMhfg7o6zMRy+9TOVein3wfdXnsZib2cLDGRBxTSaU05YFQn8oW8w1P5Aj5pY0davMtQZIY2ial9h+HvqUzxO2j59YTNcTlb+f/gfCoGWEfjZDeA+k9Z6uz5PjhL0Zvd6xCI/rezVNEJ7S3yUIP+2e/eIE4d97GJ+aILzco9f7U4Q/9uxztFjY2ku/3yK8m3v3dyXCAcNqKOqDvvO/LRYevvLKDRbhqSvx12y/zDO8Xiz8vr9+j0V4YcDdRycIzw3sBOaeHVK/carwi6FrdGeKhWPDsv/TInQM+z3U4fHh+mNm4VfD+/zGIvxheC9B2DRcf9Qs7CDAu8N7QIlHET45XL/fLJwd3gcKDI8A4LER+n1m4d9HILBhRA8obyPC7SP0r5uFvQT+EIHPR+h3m4UzBFg7cuw/zMLmkdlQiVdGOuD7+sI+Z8cKnxVe2zxW+Ot14qki4fExPX5SJNxX1OeTIuEnRf9mUGTYr8qwXyfU1KGi9YBv+3V5BJ8gbAc2tusMH/QSDujOgAx2ZRn25ApfZBteyxVW5bwKyKv67F/nCr/pNfi9XiDFPTolz4F5ho5sYWS/1dmCb+xXWcL/yezxdJbwTOZbGfT5UHQk1a26P2QKh3WTgOeMaaBp72cMXZspnMv4VZfzuQpf5DlB/4BOuB4U4WZ9s064xdqVtP/6/Ovzr8+/Pv/6/M991g1i8xs2n2kcZP2XUP4/+ujShO/kqOkPNfR5RivvfM7Lo+2uvOu5XxWllXcYK/eGDeTurRG4dxmXsOfK/EZ5V/VX52N+8r7bDGv8Pdxkvq23xt8rTmj2XHln9ZfsJdjKu6qVdyxfqeE//i5u9r5kZRyhnecq79RW3uFs6mtV4eY+VlW9T7Gwu6b88zHKT2NvKxsPUVqpxylGHzf+79pR/B47zWc6a+f5LKxj4VIWPsDCx1j4NAufZ+EOFr7Nwk9YeIaFOex+oKtYOIKFE1k4nYXzWVjHwqUsfICFj7HwaRY+z8IdLHybhZ+w8AwLc9g9QVexcAQLJ7JwOgvns7COhUtZ+AALH2Ph0yx8noU7WPg2Cz9h4RkW5jA/ehULR7BwIguns3A+C+tYuJSFDwxMrTczyssnmwrm1YR8cshUUlRcZB5jCRHK8iNLSZG5uJCigsvr9C0xLXUHgrhVaDEXwX9jilVRi8aZLqg7meAllPsa1XhG/J5DNZ4pyCnxrLjdq/HsuL2r8Zy4X1Dj3VLaUyZYq2KHarx73J7VeI+43avxK+L+T433FMwp8V7x/lKN58b9pho3CKaUuDF+/6Ma7y2YFqfC+wi4HJSM9437ZzXeL+6X1Xjifi81flVKv5EJXlO5H0KN58X9rhrvL2y5KxWeuN9LjQ9Mwp7HNRHhi1jq/i5ZDn0ZvlqDD2c4LvHwnxKGL9DgM5X8Nfgihj+qwe9iOC6R8Z8mhh/Q4D9luFGTzzOk70rolfLu/ZcUnP72QTjHOrhvGa6sRyvv0sd3eCGurIsr+GKGK+vYyt0BjzL81BSKH2f4ZoYLsyn+M4afYHhjBcUHswHF1RksvkNdz7kMXzdbjbcxfK2mnhsZforhyvW0uZnY9gOELwOLVeOYkkwaf841NP7P2eUHjzH8yFSKr2EdfWEWw5kcBrL6yFk0/y80+TcR3BDfB1DGAX9iuLIfoeCfMHyxBu+fTfHlGnw2w9dq8B8yXNTg/8FwZb9CuYPg7wxX9m+UOwV65lD8SQ1+I8OVfRrlbpcQw5V9GuVuhV8zXNkHUu5Q2Mtwq6SOH2P4vkVqfFw3iq/X4Iu6pbZ3TzemV5p5yZ0MN2vwHzFcO495tBtt31Oa9v0NwZP95C6WzzpNPm+T+Mn+Nl39vyLxewtyCr+dKn6mno6utf3CVXrMJ9k/D9FT76etv5nh2nqWk3yS/fYt+tT3TXrT4PemwZ/QY+37C/s0fv5X+tT3Sr6YJp8rc/FekuR+JLd7mvtEu2P+iX5WuYvn+jTxbyY4+E/Wvj9h+Pw08X+YBn86DX4O65PRX9ipqX/3Hmnu/e2R+l5Md5r4q9Lgv0iDb0+Dj+mDePK45ROMnwF+mPVHyrzqfJp8el+RGg+kwR9Kg69Lg/fPpe2l3F+u7E3uTBP/gzT4yStS32N6Zc/U8Uf2TH3f6rI08X9uQDx5PPlgT6oPWrt4LE0+p9Pg+b3S6GcafE0a/E+9Ut+3uitN/EO9Ut8v2zeX2rvWTkcRPzBA6AyocVNumnuy0+Bz0+DuXJq/Vp53pYn/VBpcMKTGh6fBf5QGX2ug+onXc5D6KfqcJv6pNHimMTXuTINvSYO/ZUx9b+6ZNPHn906N/yoN/pc0+N40+LA+VD7GKrU/Gd8ndfzqNHiwT+r7jH/cJ/U9yuv6pL6feHuf1PcfR/qkvre4uG+a+8j7prmHGO9BpNdOSrKzxus2JyGWZCQFNC4ZGp8MFSdByemSk5UI8bMywVCNZJfqilyNjXgfZZdP0ZSPs99UNq5Uwhs3KxrnzqRXE3c5eYWZXrJ6KUeWLivNuC6kGR+UgR8bu+v0glGL8chrMR55tXm9XYvdpSooB8qoWCdeilhVScePv5ykF5MsOWdtMSfOWdur5In0TLN9VpVZSogRrzqtmiBhFS7MdklNyOOVPb5g8Sy/z00v4rVYJIkd75PqivFWUZfXfvGmg8KwEsXkMu1qyWaxBNzBkFcmF27bZldNkmjuF6kIZjWpLuRDriYEG70eGUq/ScMeMlbt8gYDqdPbaMJgI0YBoNY2qc4fWOYM1GLF6hqJYBpnV5V0rUpKdYo9PlmC2sxNqo13NmnmKtlRIkkeP94eTm5jvpTjcF2Irz072JUkmnOMXUiS4rDkxVMljmJePG6pmoWqS5RS1aVLqerSpVR1WVKqugQpVV2SlOZfopTmX7qU5ne18q6AHJRDddBdCbXugHuJJyi7A5LcAMYBXiQoSFKtX1ri9dc4vVItGE5QcoaWCy5/Q6PXLbtriyaVlk5KHUmqA9uRnIGAc4UEgg2sEOoCzga3VBtqaFgBSThKQitTRZWk6XPLKm2SbVaFBOYozZg1T7KJDBQr5gpSxS2zyirt5fBMlbhWDZDrlON98+zp06ts1VJ12TSHTaJXOlut/A3I0q0+ZwOD2F3J5Erp8Y0h2ebSPHDjry9UV3Ynp/y+F5WrcsRrnJPvsdcUap8tkR/iSaGgu5ZdSK1mklwuza6opj+G4a71tlq5K6SRt3Hm+CXmbt8SuT5+i/k/i1nu/u5kbqXaoF+qB4P2ulNe562tRPV8KCtxUbrb2ZDmonSbJiV/sbdWJ7g7xbXlpb/kXZt/8g3qalHXemEYwFoDtFaGrBo9bnZveKJGFq2oSymzfiprynN6iZdbbHgvvGQHBZoNWtbgr3WnkHri+nKtLLAJUhgItiR0ryBBu9dmm1vlr9Y0Zim7+jzJ3palsDftzfUVFq3k8cp0bVbV1ZcvF1uSEMi17ZoipOrKcsUlYdNPlEj+kLPCfCpNm4v8JGqD9QAfZJZsVROlOTOrxkterahwJFMlT3CR8ZfLBu1VKS3z1Lp9xLVpZIGXwF+W9UEPwf12zdbgSpYB/kRNK2bKN1X5Gmet5HIG5RR2Uezyh5LMs9aZrD3YV5lJ1Z01nqUW9DdBD3Q/YJBkvAk81/ltamOR0PUy5w7Vl/0pbFaeiNYEs4Uk5anDH9xpm7YGimO9BXq9YoVF4ELy10kwgl7iluoaZDDtlRpBmVmDXXIDjIcushb6yUAQyyAO/2Iev9gOGlBusS39J7hfEHslOJ1Gr9PltjU0pOxv6tz+Oq2ovJ4al+QKhiQ2OL6Moiexn6/aUpS4xC0HUzSnxieADObOvIySbakEfDmNN5E0HqipLEF3lL79wIM3+JdqHZ+0ZPlyqdEdCPp9TpjfrJCWmjVd72VVahKnUResFREp85GgWykd1wSX1+0MYIcxjnQY8A86Jneqno0Nf3gG5vmWYV3mwsyxAdOUl0N88+UPFFxgtbLbNjcVMwmVxEEnY87NL1loK00SEHuXcDyU1JfY+Qy0iZc0+H0sscRaKhG5eFm9U062T8xRo8IpPCEnmgm8aNKMYtKrNPSrFx4pJTmVZD8pFAVXNMjOGgjBx5KwXvkG82d3oFEogvzdRdDmY2TnEkYt8YWKcL5dO8ZTKxCq3hmsF4pqV/ggPxrKAfqEna5RERI8g6GQEyOyb41eGYsEb1MEoxL4S5q5KOAnQ/Aidz2bTdTXBhIUZOpyqVbpaB50akDzUL5jPlgUZEkq6GzwuCC9XyZ/aPm0LOgnhCKY/+Bk8Z9yvmwg28NT1nGV80IlDBiU5pxifD2Ynb1T0ivniqoZYEraK1V/LJr0yvkjmQH5F0mPv4M5E4v5lfTKOaUnGHA7w7M15xmVzyx2NjFDc36xUwFyEoGOS6+sM89nZwYzNOchO/Xq84/p5LeInT1U0ivno46zBfFVmvpnaMI72VlGhVbOUTX2ZvsKHBuZKfhfyWSaoTk/ae6jPj+plZ/CfzNLP01zHtPUV31+M5ul0aZfw2SSozm/mpenPueZrv3DmvTKOS8zS784Ux3fqAkf1aRXzu2sZUeZ7p+UOn18n1CTXtl/7VelPnearv7rNPan7HubWHqxpzq+tv3Wa9Ir5w3qJUo/d5Hyn9eWz86rmdh23IKsC5e/RZNeOc+1vJbSUzMuXP5+PAvAnbtVzjkUeFPLW68JD9Gtv3h65fxEiTd1fbXpj7P6K+mVcw1Wln69xmC1/uwsZ1v8ed1Ig9pQczTlGjmHwJevnM+L+LvGf7Ymffw8SCNrH92F0+dq0iv7v1vuunD5yqefjmJKemUfeh9Ln3cR+fVn5Zs1uJJ+ThfOyaf6zZkpwOyf/hSPnJObn8L/dOdlx5/LuI/5x74X9t+906T/5lEaXqu7cPr/B/xOtBXgnQAA'
    bin = gzip.decompress(base64.b64decode(gz))
    with open(pymain, "wb") as f:
        f.write(bin)
    os.chmod(pymain, 0o775)

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline

H,W=map(int,input().split())
D=[tuple(map(int,input().split())) for i in range(H)]

# 範囲更新、最大値取得の遅延セグ木と、範囲更新、最小値取得の遅延セグ木

seg_el=1<<((W+3).bit_length()) # Segment treeの台の要素数
SEG=[1<<30]*(2*seg_el) # 1-indexedなので、要素数2*seg_el.Segment treeの初期値で初期化
LAZY=[0]*(2*seg_el) # 1-indexedなので、要素数2*seg_el.Segment treeの初期値で初期化

SEG2=[0]*(2*seg_el) # 1-indexedなので、要素数2*seg_el.Segment treeの初期値で初期化
LAZY2=[0]*(2*seg_el) # 1-indexedなので、要素数2*seg_el.Segment treeの初期値で初期化

def indexes(L,R):
    INDLIST=[]

    R-=1
    
    L>>=1
    R>>=1

    while L!=R:
        if L>R:
            INDLIST.append(L)
            L>>=1
        else:
            INDLIST.append(R)
            R>>=1

    while L!=0:
        INDLIST.append(L)
        L>>=1

    return INDLIST
        

def updates(l,r,x): # 区間[l,r)をxに更新
        
    L=l+seg_el
    R=r+seg_el

    L//=(L & (-L))
    R//=(R & (-R))

    UPIND=indexes(L,R)
    
    for ind in UPIND[::-1]:
        if LAZY[ind]!=None:
            LAZY[ind<<1]=LAZY[1+(ind<<1)]=SEG[ind<<1]=SEG[1+(ind<<1)]=LAZY[ind]
            LAZY[ind]=None
    
    while L!=R:
        if L > R:
            SEG[L]=x
            LAZY[L]=x
            L+=1
            L//=(L & (-L))

        else:
            R-=1
            SEG[R]=x
            LAZY[R]=x
            R//=(R & (-R))

    for ind in UPIND:
        SEG[ind]=max(SEG[ind<<1],SEG[1+(ind<<1)])

def updates2(l,r,x): # 区間[l,r)をxに更新
        
    L=l+seg_el
    R=r+seg_el

    L//=(L & (-L))
    R//=(R & (-R))

    UPIND=indexes(L,R)
    
    for ind in UPIND[::-1]:
        if LAZY2[ind]!=None:
            LAZY2[ind<<1]=LAZY2[1+(ind<<1)]=SEG2[ind<<1]=SEG2[1+(ind<<1)]=LAZY2[ind]
            LAZY2[ind]=None
    
    while L!=R:
        if L > R:
            SEG2[L]=x
            LAZY2[L]=x
            L+=1
            L//=(L & (-L))

        else:
            R-=1
            SEG2[R]=x
            LAZY2[R]=x
            R//=(R & (-R))

    for ind in UPIND:
        SEG2[ind]=min(SEG2[ind<<1],SEG2[1+(ind<<1)]) 
        
def getvalues(l,r): # 区間[l,r)に関するmaxを調べる

    L=l+seg_el
    R=r+seg_el

    L//=(L & (-L))
    R//=(R & (-R))

    UPIND=indexes(L,R)
    
    for ind in UPIND[::-1]:
        if LAZY[ind]!=None:
            LAZY[ind<<1]=LAZY[1+(ind<<1)]=SEG[ind<<1]=SEG[1+(ind<<1)]=LAZY[ind]
            LAZY[ind]=None
            
    ANS=-1

    while L!=R:
        if L > R:
            ANS=max(ANS , SEG[L])
            L+=1
            L//=(L & (-L))

        else:
            R-=1
            ANS=max(ANS , SEG[R])
            R//=(R & (-R))

    return ANS

def getvalues2(l,r): # 区間[l,r)に関するminを調べる

    L=l+seg_el
    R=r+seg_el

    L//=(L & (-L))
    R//=(R & (-R))

    UPIND=indexes(L,R)
    
    for ind in UPIND[::-1]:
        if LAZY2[ind]!=None:
            LAZY2[ind<<1]=LAZY2[1+(ind<<1)]=SEG2[ind<<1]=SEG2[1+(ind<<1)]=LAZY2[ind]
            LAZY2[ind]=None
            
    ANS=1<<31

    while L!=R:
        if L > R:
            ANS=min(ANS , SEG2[L])
            L+=1
            L//=(L & (-L))

        else:
            R-=1
            ANS=min(ANS , SEG2[R])
            R//=(R & (-R))

    return ANS

for i in range(W+1):
    updates(i,i+1,i)

for i in range(H):
    x,y = D[i]
    if x==1:
        updates(x,y+1,-1<<30)
    else:
        MAX=getvalues(1,x)
        updates(x,y+1,MAX)

    updates2(x,y+1,1<<30)
    updates2(y+1,y+2,y+1-getvalues(y+1,y+2))

    #print(*[getvalues(i,i+1) for i in range(W+1)])
    #print(*[getvalues2(i,i+1) for i in range(W+1)])

    ANS=getvalues2(1,W+1)+i+1
    if ANS>1<<28:
        print(-1)
    else:
        print(ANS)

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline

H,W=map(int,input().split())
D=[tuple(map(int,input().split())) for i in range(H)]

# 範囲更新、最大値取得の遅延セグ木と、範囲更新、最小値取得の遅延セグ木

seg_el=1<<((W+3).bit_length()) # Segment treeの台の要素数
SEG=[1<<30]*(2*seg_el) # 1-indexedなので、要素数2*seg_el.Segment treeの初期値で初期化
LAZY=[0]*(2*seg_el) # 1-indexedなので、要素数2*seg_el.Segment treeの初期値で初期化

SEG2=[0]*(2*seg_el) # 1-indexedなので、要素数2*seg_el.Segment treeの初期値で初期化
LAZY2=[0]*(2*seg_el) # 1-indexedなので、要素数2*seg_el.Segment treeの初期値で初期化

def indexes(L,R):
    INDLIST=[]

    R-=1
    
    L>>=1
    R>>=1

    while L!=R:
        if L>R:
            INDLIST.append(L)
            L>>=1
        else:
            INDLIST.append(R)
            R>>=1

    while L!=0:
        INDLIST.append(L)
        L>>=1

    return INDLIST
        

def updates(l,r,x): # 区間[l,r)をxに更新
        
    L=l+seg_el
    R=r+seg_el

    L//=(L & (-L))
    R//=(R & (-R))

    UPIND=indexes(L,R)
    
    for ind in UPIND[::-1]:
        if LAZY[ind]!=None:
            LAZY[ind<<1]=LAZY[1+(ind<<1)]=SEG[ind<<1]=SEG[1+(ind<<1)]=LAZY[ind]
            LAZY[ind]=None
    
    while L!=R:
        if L > R:
            SEG[L]=x
            LAZY[L]=x
            L+=1
            L//=(L & (-L))

        else:
            R-=1
            SEG[R]=x
            LAZY[R]=x
            R//=(R & (-R))

    for ind in UPIND:
        SEG[ind]=max(SEG[ind<<1],SEG[1+(ind<<1)])

def updates2(l,r,x): # 区間[l,r)をxに更新
        
    L=l+seg_el
    R=r+seg_el

    L//=(L & (-L))
    R//=(R & (-R))

    UPIND=indexes(L,R)
    
    for ind in UPIND[::-1]:
        if LAZY2[ind]!=None:
            LAZY2[ind<<1]=LAZY2[1+(ind<<1)]=SEG2[ind<<1]=SEG2[1+(ind<<1)]=LAZY2[ind]
            LAZY2[ind]=None
    
    while L!=R:
        if L > R:
            SEG2[L]=x
            LAZY2[L]=x
            L+=1
            L//=(L & (-L))

        else:
            R-=1
            SEG2[R]=x
            LAZY2[R]=x
            R//=(R & (-R))

    for ind in UPIND:
        SEG2[ind]=min(SEG2[ind<<1],SEG2[1+(ind<<1)]) 
        
def getvalues(l,r): # 区間[l,r)に関するmaxを調べる

    L=l+seg_el
    R=r+seg_el

    L//=(L & (-L))
    R//=(R & (-R))

    UPIND=indexes(L,R)
    
    for ind in UPIND[::-1]:
        if LAZY[ind]!=None:
            LAZY[ind<<1]=LAZY[1+(ind<<1)]=SEG[ind<<1]=SEG[1+(ind<<1)]=LAZY[ind]
            LAZY[ind]=None
            
    ANS=-1

    while L!=R:
        if L > R:
            ANS=max(ANS , SEG[L])
            L+=1
            L//=(L & (-L))

        else:
            R-=1
            ANS=max(ANS , SEG[R])
            R//=(R & (-R))

    return ANS

def getvalues2(l,r): # 区間[l,r)に関するminを調べる

    L=l+seg_el
    R=r+seg_el

    L//=(L & (-L))
    R//=(R & (-R))

    UPIND=indexes(L,R)
    
    for ind in UPIND[::-1]:
        if LAZY2[ind]!=None:
            LAZY2[ind<<1]=LAZY2[1+(ind<<1)]=SEG2[ind<<1]=SEG2[1+(ind<<1)]=LAZY2[ind]
            LAZY2[ind]=None
            
    ANS=1<<31

    while L!=R:
        if L > R:
            ANS=min(ANS , SEG2[L])
            L+=1
            L//=(L & (-L))

        else:
            R-=1
            ANS=min(ANS , SEG2[R])
            R//=(R & (-R))

    return ANS

for i in range(W+1):
    updates(i,i+1,i)

for i in range(H):
    x,y = D[i]
    if x==1:
        updates(x,y+1,-1)
    else:
        MAX=getvalues(1,x)
        updates(x,y+1,MAX)

    updates2(x,y+1,1<<30)
    updates2(y+1,y+2,y+1-getvalues(y+1,y+2))

    #print(*[getvalues(i,i+1) for i in range(W+1)])
    #print(*[getvalues2(i,i+1) for i in range(W+1)])

    ANS=getvalues2(1,W+1)+i+1
    if ANS>1<<28:
        print(-1)
    else:
        print(ANS)

Submission status: Wrong Answer

Solution code:
class segTree:
  inf = 10**18
  def __init__(s, num):
    s.N = 1
    while s.N < num:
      s.N *= 2
    s.T = [0] * (2 * s.N)
    s.L = [0] * (2 * s.N)
  def do(s, l, r):
    #最小値
    return min(l, r)
  def set(s, L):
    for i in range(len(L)):
      s.update(i + 1, L[i])
  def update(s, x, v):
    k = x + s.N - 1
    s.T[k] = v
    while k > 0:
      k = (k - 1) // 2
      s.T[k] = s.do(s.T[2*k+1], s.T[2*k+2])
  def get(s, x):
    s.propagates(*s.getIndex(x, x + 1))
    return s.T[x + s.N - 1]
  def getV(s, l, r):
    s.propagates(*s.getIndex(l, r))
    L = l + s.N
    R = r + s.N
    p = s.inf
    while L < R:
      if R & 1:
        R -= 1
        p = s.do(p, s.T[R - 1])
      if L & 1:
        p = s.do(p, s.T[L - 1])
        L += 1
      L >>= 1
      R >>= 1
    return p
  def getIndex(s, l, r):
    L = l + s.N
    R = r + s.N
    lm = (L // (L & -L)) >> 1
    rm = (R // (R & -R)) >> 1
    while L < R:
      if R <= rm:
        yield R
      if L <= lm:
        yield L
      L >>= 1
      R >>= 1
    while L:
      yield L
      L >>= 1
  def propagates(s, *ids):
    for i in reversed(ids):
      v = s.L[i - 1]
      if not v: continue
      s.L[2 * i - 1] += v
      s.L[2 * i] += v
      s.T[2 * i - 1] += v
      s.T[2 * i] += v
      s.L[i - 1] = 0
  # 区間加算
  def addArea(s, l, r, x):
    L = s.N + l
    R = s.N + r
    while L < R:
      if R & 1:
        R -= 1
        s.L[R - 1] = min(inf, s.L[R - 1] + x)
        s.T[R - 1] = min(inf, s.T[R - 1] + x)
      if L & 1:
        s.L[L - 1] = min(inf, s.L[L - 1] + x)
        s.T[L - 1] = min(inf, s.T[L - 1] + x)
        L += 1
      L >>= 1
      R >>= 1
    for i in s.getIndex(l, r):
      s.T[i - 1] = s.do(s.T[2 * i - 1], s.T[2 * i]) + s.L[i - 1]
  # 区間更新
  def updateArea(s, l, r, x):
    *ids, = s.getIndex(l, r)
    s.propagates(*ids)
    L = s.N + l
    R = s.N + r
    while L < R:
      if R & 1:
        R -= 1
        s.L[R - 1] = s.T[R - 1] = x
      if L & 1:
        s.L[L - 1] = s.T[L - 1] = x
        L += 1
      L >>= 1
      R >>= 1
    for i in ids:
      s.T[i - 1] = s.do(s.T[2 * i - 1], s.T[2 * i])

H, W = list(map(int, input().split()))
AB = [list(map(int, input().split())) for _ in range(H)]

seg = segTree(W)
segL = segTree(W)

inf = 10 ** 18
for i in range(H):
  a, b = AB[i]
  a -= 1
  b -= 1
  if a == 0:
    s = inf
  else:
    s = min(inf, seg.get(a - 1) + 1)
  while a <= b:
    toa = segL.get(a)
    if toa == 0:
      seg.update(a, min(inf, seg.get(a) + s))
      segL.update(a, b + 1)
      s = min(inf, s + 1)
      a += 1
    else:
      t = s - seg.get(a)
      seg.addArea(a, min(b + 1, toa), min(inf, t))
      segL.updateArea(a, min(b + 1, toa), b + 1)
      a = toa
      if a > b: break
      s = seg.get(a - 1)

  ans = seg.getV(0, W) + i + 1
  if ans >= inf:
    print(-1)
  else:
    print(ans)