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

「ICPC World Finals 2017」Visual Python++

题目描述

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

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

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

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

输入格式

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

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

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

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

输出格式

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

样例 1

2
4 7
9 8
14 17
19 18
2
1
2
4 7
14 17
9 8
19 18
1
2
2
4 8
9 7
14 18
19 17
syntax error
3
1 1
4 8
8 4
10 6
6 10
10 10
syntax error