P11329 [NOISG 2022 Finals] Towers

### SPJ 已修复。

兔子 $\text{Benson}$ 喜欢塔楼。在他的国家中有 $N$ 座城市，其中第 $i$ 座城市在坐标系中的位置为 $(X_i,Y_i)$。**没有两座城市在同一位置。** $\text{Benson}$ 希望在这 $N$ 座城市中的一些城市修建塔楼，使得下面的条件全部满足： - 对于所有的整数 $a$，最多有两座塔楼的 $x$ 坐标为 $a$； - 对于所有的整数 $b$，最多有两座塔楼的 $y$ 坐标为 $b$； - 这 $N$ 座城市要么修建了塔楼，要么处在一条与坐标轴平行的线上的两座塔楼中间。换句话说，假设一个城市在 $(x,y)$，如果这座城市没有塔楼，那么需要有两座塔楼在 $(x,c)$ 和 $(x,d)$，其中 $c \le y \le d$，或者有两座塔楼在 $(e,y)$ 和 $(f,y)$，使得 $e \le x \le f$。 $\text{Benson}$ 知道肯定有一种可行的方案，但他不知道这种方案是什么。请你帮他找出符合条件的建造方案。

第一行，一个正整数 $N$； 接下来 $N$ 行，每行两个整数 $X_i,Y_i$。

一行一个长度为 $N$ 的 $01$ 串 $A_1A_2\dots A_n$，表示你的建造方案。$A_i$ 为 $1$ 表示第 $i$ 个城市建塔楼，反之亦然。 **如果有多种可行的方案，你可以输出任意一种。**

**【样例 #1 解释】** 在第 1 和第 2 座城市建塔楼，第 3 座城市与他们有相同的 $x$ 坐标，且位于这两座城市之间。 一种不符合要求的建设方法是`111`，它违反了最多有两座塔楼的 $x$ 坐标为 $1$ 的限制。 另一种不符合要求的建设方法是`101`，第 2 座城市尽管与第 1、3 座城市有相同的 $x$ 坐标，但并不位于他们之间的线段上。 **【数据范围】** |$\text{Subtask}$|分值|特殊性质| |:-:|:-:|:-:| |$0$|$0$|样例| |$1$|$5$|$N\le3$| |$2$|$11$|$N\le16$| |$3$|$7$|$N=ab$，其中 $a$ 和 $b$ 是两个正整数，且对于所有满足 $0 \le i \le b-1,1 \le j \le a$ 的整数 $i,j$，有 $(X_{ai+j},Y_{ai+j})=(i+1,j)$| |$4$|$6$|对于所有整数 $a$，最多有两座城市的 $x$ 坐标为 $a$| |$5$|$31$|$N\le5000$| |$6$|$21$|$N\le100000$| |$7$|$19$|无| 对于 $100\%$ 的数据，$1 \le N \le 10^6, 1 \le X_i,Y_i \le 10^6$，保证对于所有 $1 \le i < j \le n$ 都有要么 $X_i\not=X_j$，要么 $Y_i\not=Y_j$。