← 返回题目列表

Codeforces · 429/E

E. 点和段

中文机器翻译题面 查看原题

Iahub在几何题上准备得并不充分,但他听说今年IOI选拔营里会有很多几何题。由于害怕,Iahub 将自己锁在地下室里,开始思考此类新问题。其中之一如下。

Iahub 希望在 OX 轴上绘制 n 个不同的线段 [li, ri]。他可以用红色或蓝色绘制每个部分。当且仅当满足以下要求时,绘图才是好的:对于 OX 轴的每个点 x,考虑包含点 x 的所有线段;假设 rx 红色线段和 bx 蓝色线段包含点 x;对于每个点 x 不等式 |rx - bx|必须满足≤1。

线段 [l, r] 包含点 x 当且仅当 l ≤ x ≤ r。

Iahub 为您提供所有段的起点和终点。你得给他找个好画。

输入

输入的第一行包含整数 n (1 ≤ n ≤ 105) — 段数。接下来 n 行的第 i 行包含两个整数 li 和 ri (0 ≤ li ≤ ri ≤ 109) — 第 i 段的边界。

保证所有段都是不同的。

输出

如果给定测试没有好的绘图,则输出单个整数 -1。否则输出n个整数;每个整数必须为 0 或 1。第 i 个数字表示第 i 段的颜色(0 为红色,1 为蓝色)。

如果有多张好图,您可以输出其中任何一个。

示例

输入 #1

2
0 2
2 3

输出 #1

0 1

输入 #2

6
1 5
1 3
3 5
2 10
11 11
12 12

输出 #2

0 1 0 1 0 0