Background

2024GDKOI pj day2

Description

现在，在笛卡尔坐标系（无限大二维平面）上有 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 种细菌，询问其占领面积能否趋于无穷大。

Format

Input

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

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

Output

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

Samples

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 夹的中间部分，面积趋于无穷大。

Limitation

对于 25% 数据,n ≤ 10^2。

对于 50% 数据,n ≤ 10^3。

对于 75% 数据,n ≤ 10^5。

对于 100% 数据,n ≤ 10^6 , −10^9 ≤ xi , yi ≤ 10^9。