{"raw_statement":[{"iden":"problem statement","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."},{"iden":"constraints","content":"*   $1 \\leq H,W \\leq 2\\times 10^5$\n*   $1 \\leq A_i \\leq B_i \\leq W$"},{"iden":"input","content":"Input 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$"},{"iden":"sample input 1","content":"4 4\n2 4\n1 1\n2 3\n2 4"},{"iden":"sample output 1","content":"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."}],"translated_statement":null,"sample_group":[],"show_order":["default"],"formal_statement":null,"simple_statement":null,"has_page_source":true}