#6481. 「ICPC World Finals 2017」Visual Python++

内存限制:1024 MiB 时间限制:5000 ms 标准输入输出
题目类型:传统 评测方式:Special Judge
上传者: tangjz

题目描述

在最近被提出的 Visual Python++ 编程语言中,一个语句块被表示为一个由字符组成的矩形,其中左上角在 r_1 c_1 列,右下角在 r_2 c_2 列。对于 r_1 \leq r \leq r_2 , c_1 \leq c \leq c_2 ,所有位于 (r, c) 的字符被认为是属于这个块的内容。在这些位置中,满足 r = r_1 r = r_2 c = c_1 c = c_2 的位置被称为是边界。

语句块可以嵌套(矩形包含在其他矩形中)任意层。在语法正确的程序中,任意两个语句块要么是嵌套的(一个包含在另一个中),要么是不交的(不重叠)。在这两种情况中,他们的边界也不能重叠。

编程人员不需要画出经典程序中的所有矩形,这太浪费时间了,而且 Visual Python++ 也不可能称为下一个 ICPC 编程语言。因此程序员只需要在左上角位置放一个字符 ,在右下角位置放一个字符 。解析器会自动匹配相应的拐角来获取程序的嵌套结构。

你的团队刚刚获得了五小时的合同来开发解析器的这一部分。

输入格式

第一行包含一个整数 n (1 \leq n \leq 10^5) ,表示拐角对的数量。

接下来 n 行,每行包含两个整数 r c (1 \leq r, c \leq 10^9) ,指定 r c 列为一个左上角。

接下来 n 行以相同的方式指定了右下角。

所有的拐角位置互不相同。

输出格式

输出 n 行,每行包含一个整数。第 i 行的整数 j 表示第 i 个左上角和第 j 个右下角组成一个矩形。左上角和右下角均按照他们在输入中的顺序从 1 n 标号。输出必须是 1 n 的排列,从而匹配可能嵌套的矩形。如果存在超过一种合法的匹配,任意一组合法的匹配都是可接受的。如果不存在合法的匹配,输出 syntax error

样例

样例输入 1

2
4 7
9 8
14 17
19 18

样例输出 1

2
1

样例输入 2

2
4 7
14 17
9 8
19 18

样例输出 2

1
2

样例输入 3

2
4 8
9 7
14 18
19 17

样例输出 3

syntax error

样例输入 4

3
1 1
4 8
8 4
10 6
6 10
10 10

样例输出 4

syntax error