U189505 布置报告厅

小成的学校最近建了一个简陋的报告厅，又有很多一样的椅子要放到正确的位置，学校委$(qiang)$托$(po)$小成去帮忙布置一下。 小成是个热爱编程的乐于助人的好学生，所以小成请你帮他算一下，假如小成搬动所有椅子花费力气一样，分别应该将哪个椅子搬向哪里，才能让小成搬动所有椅子花费力气的总和最小。 由于某些原因，小成只能往上、下、左、右移动。也就是说，要斜着移动，会花费 $2$ 步。

$%报告厅放在平面上时，它的4个角分别在 \$( x_1 , y_1 ) , ( x_1 , y_2 ) , ( x_2 , y_1 ) , ( x_2 , y_2 )\$ 。$ 有n张椅子，分别在 $(st$-$x_1,st$-$y_1),(st$-$x_2,st$-$y_2),(st$-$x_3,st$-$y_3),......,(st$-$x_n,st$-$y_n)$ ，要搬$%^①$到 $(ed$-$x_1,ed$-$y_1),(ed$-$x_2,ed$-$y_2),(ed$-$x_3,ed$-$y_3),......,(ed$-$x_n,ed$-$y_n)$ 。 $%------------$ $%### 注释$ $%_①$$%_不$$%_一$$%_定$$%_按$$%_顺$$%_序$$%_一$$%_一$$%_对$$%_应$

第一行输入一个正整数 $n$ 。 $%第二行输入 \$x_1,x_2,y_1,y_2\$ ，用空格隔开。$ 接下来 $n$ 行，其中的第i行输入 $st$-$x_i,st$-$y_i$，用空格隔开。 接下来 $n$ 行，其中的第i行输入 $ed$-$x_i,ed$-$y_i$，用空格隔开。

输出共 $n$ 行。 第i行输出坐标为 $(st$-$x_i,st$-$y_i)$ 的数应搬到哪个编号的位置。若输出 $r$ ，表示 $(st$-$x_i,st$-$y_i)$ 的椅子应搬到 $(ed$-$x_r,ed$-$y_r)$ 。 如果有多种方法耗费相同，因为小成比较喜欢二分，所以输出康托展开值第 $⌊\frac{S+1}{2}⌋$ 小的，其中S为所有耗费最小的搬法的个数。

## 数据范围 $01$ 。 将 $(1,1)$ 的椅子搬向 $(2,3)$ ，耗费 $3%\sqrt5>2$ 。 总耗费为 $5%\sqrt5+\sqrt2>3$ 。 将 $(2,2)$ 的椅子搬向 $(2,3)$ ，耗费 $1$ 。 将 $(1,1)$ 的椅子搬向 $(1,3)$ ，耗费 $2$ 。 总耗费为 $3$ 。 所以选择更小的第一种，输出： ``` 2 1 ``` 。 ### #3 将 $(-3,3)$ 的椅子搬向 $(-3,-3)$ ，耗费 $6$ 。 将 $(3,-3)$ 的椅子搬向 $(0,0)$ ，耗费 $6%3\sqrt2$ 。 总耗费为 $12%6+3\sqrt2$ 。 同样地， 将 $(-3,3)$ 的椅子搬向 $(0,0)$ ，耗费 $6%3\sqrt2$ 。 将 $(3,-3)$ 的椅子搬向 $(-3,-3)$ ，耗费 $6$ 。 总耗费为 $12%6+3\sqrt2$ 。 因为 $1\ 2$ 康托展开值为 $1$ ， $2\ 1$ 的康托展开值为 $2$ ，所以输出第 $\lfloor\frac{2+1}{2}\rfloor$ 小的，为： ``` 1 2 ``` 。 ## 数据范围 | $#$ | $n=$ | $x,y≤$ | 分值 | | :----------: | :----------: | :----------: | :----------: | | $1$ | $5$ | $10$ | $5$ | | $2$ | $15$ | $100$ | $5$ | | $3$ | $50$ | $150$ | $6$ | | $4$ | $50$ | $300$ | $6$ | | $5$ | $100$ | $1000$ | $6$ | | $6$ | $250$ | $1000$ | $7$ | | $7$ | $500$ | $10^4$ | $7$ | | $8$ | $1000$ | $10^9$ | $8$ | | $9$ | $750$ | $5\times10^5$ | $7$ | | $10$ | $750$ | $5\times10^6$ | $7$ | | $11$ | $900$ | $10^7$ | $7$ | | $12$ | $950$ | $5\times10^7$ | $7$ | | $13$ | $1000$ | $10^8$ | $7$ | | $14$ | $1000$ | $10^9$ | $8$ | | $15$ | $4$ | $10^9$ | $7$ | [主体部分提示](https://www.luogu.com.cn/paste/j5qa4tdq)