Puzzle

문제

Zigmas has a rectangular jigsaw puzzle of height $HH$ and width $WW$. The puzzle consists of $NN$ pieces. Each piece is constructed from $HH$ rectangles of unit height stacked on one another. The pieces are shuffled, but neither rotated nor flipped.

Help Zigmas solve the puzzle by writing down how to order the pieces to get a perfect rectangle. The pieces can't be rotated or flipped, they can't overlap and there must be no gaps left.

입력

The first line contains two integers $NN$ and $HH$ ($2\le N,H,N\cdot H\le 2000002\; \backslash le\; N,\; H,\; N\; \backslash cdot\; H\; \backslash le\; 200\backslash ,000$): the number of puzzle pieces and the puzzle height, respectively.

Each of the remaining $NN$ lines contains $2\cdot H2\; \backslash cdot\; H$ integers: $(j+1)(j+1)$-st line describes the $jj$-th puzzle piece as $A_{j,1},B_{j,1},\dots ,A_{j,H},B_{j,H}A\_\{j,1\},\; B\_\{j,1\},\; \backslash ldots,\; A\_\{j,H\},\; B\_\{j,H\}$ (), where $A_{j,i}A\_\{j,i\}$ is the $XX$-coordinate of the left side and $B_{j,i}B\_\{j,i\}$ the $XX$-coordinate of the right side of the $ii$-th rectangle of the $jj$-th piece.

It is known that each puzzle piece is a connected figure ( and for all $1\le j\le N1\; \backslash le\; j\; \backslash le\; N$ and ).

출력

Output $NN$ distinct integers, each in the range $1\dots N1\; \backslash ldots\; N$: the numbers of the puzzle pieces in such an order that they form a perfect rectangle when laid out side by side. If there are several solutions, output any one of them. It is known that at least on soluton exists in each test case.