题目描述

现在，在笛卡尔坐标系（无限大二维平面）上有 $n$ 个种类互不相同的细菌，它们所在的坐标也互不相同。

随着时间的增加，细菌们不断繁殖，以正方形的形状、用相同的正方形扩张速度，同时扩张自己的领地。

具体来说对于任意时刻 $t$、平面上任意一点 $p$，假设该点 $p$ 上存在第 $i$ 种细菌，那么有以下两种情况：

• 如果以点 $p$ 为中心的任意正方形都含有其他种类的细菌，则该点的细菌将不会扩张（可以称之为“接触抑制”）。

• 如果存在一个以 $p$ 为中心的正方形不含有其他种类的细菌，则该点的细菌将会进行扩张。

注意，扩展出去的同种细菌也具备一样的扩展能力。

以下是一些简单的关于正方形扩展的例子：

若初始时，平面只有唯一的一个细菌位于 $(0, 0)$，那么过一个单位时间后，这一类细菌将占领 $(1, 1) (1, -1) (-1, -1) (-1, 1)$ 围成的正方形。

若初始时，平面有两个细菌分别位于 $(0, 0)$ 和 $(1, 0)$，那么最终 $(0.5, 0)$ 会成为他们领地的分界线，一开始位于 $(0, 0)$ 的细菌会占领 $(0.5, 0)$ 左侧的全部区域，位于 $(1, 0)$ 的细菌会占领 $(0.5, 0)$ 右侧的全部区域。

现在询问对于第 $i$ 种细菌，询问其占领面积能否趋于无穷大。

输入格式

第一行一个正整数 $n(1 \leq n \leq 10^6)$ 表示细菌母体的数量。

接下来输入 $n$ 行，每行输入两个整数，表示点的坐标 $(x_i, y_i)$，即种类为 $i$ 的细菌母体的位置。

输出格式

输出一个长度为 $n$ 的 $01$ 串，对于其中第 $i$ 个数字，$1$ 表示种类为 $i$ 的细菌的占领面积可以扩张到无穷大，$0$ 则表示最终面积有限。

5
0 0
2 0
2 2
0 2
1 1

11110

3
-2 0
0 0
2 0

111

7
-7 -8
5 -9
1 -5
9 -4
-8 3
-2 -3
-4 -6

1101110

提示

【样例解释】

在第二个样例，点 $(0, 0)$ 最终拥有的领地是直线 $x = -1$ 与 $x = 1$ 夹的中间部分，面积趋于无穷大。

【数据范围】

对于 $25\%$ 数据，$n \leq 10^2$。

对于 $50\%$ 数据，$n \leq 10^3$。

对于 $75\%$ 数据，$n \leq 10^5$。

对于 $100\%$ 数据，$1\leq n \leq 10^6$，$-10^9 \leq x_i, y_i \leq 10^9$。