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