{"problem":{"name":"I hate Shortest Path Problem","description":{"content":"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 intege","description_type":"Markdown"},"platform":"AtCoder","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"abc177_f"},"statements":[{"statement_type":"Markdown","content":"There is a grid of squares with $H+1$ horizontal rows and $W$ vertical columns.\nYou 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.\nFor 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.\n\n## Constraints\n\n*   $1 \\leq H,W \\leq 2\\times 10^5$\n*   $1 \\leq A_i \\leq B_i \\leq W$\n\n## Input\n\nInput is given from Standard Input in the following format:\n\n$H$ $W$\n$A_1$ $B_1$\n$A_2$ $B_2$\n$:$\n$A_H$ $B_H$\n\n[samples]","is_translate":false,"language":"English"}],"meta":{"iden":"abc177_f","tags":[],"sample_group":[["4 4\n2 4\n1 1\n2 3\n2 4","1\n3\n6\n-1\n\nLet $(i,j)$ denote the square at the $i$\\-th row from the top and $j$\\-th column from the left.\nFor $k=1$, we need one move such as $(1,1)$ → $(2,1)$.\nFor $k=2$, we need three moves such as $(1,1)$ → $(2,1)$ → $(2,2)$ → $(3,2)$.\nFor $k=3$, we need six moves such as $(1,1)$ → $(2,1)$ → $(2,2)$ → $(3,2)$ → $(3,3)$ → $(3,4)$ → $(4,4)$.\nFor $k=4$, it is impossible to reach any square in the fifth row from the top."]],"created_at":"2026-03-03 11:01:14"}}