← 返回题目列表

Codeforces · 430/A

A. 点和线段(简单)

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

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

Iahub 希望在 OX 轴上绘制 n 个不同的点和 m 个线段。他可以用红色或蓝色绘制每个点。当且仅当满足以下要求时,绘图才是好的:对于每个线段[li,ri],认为所有红点都属于它(ri 点),所有蓝点都属于它(bi 点);每个段 i 应满足不等式 |ri - bi| ≤ 1。

如果不等式 l ≤ x ≤ r 成立,则 Iahub 认为点 x 属于线段 [l, r]。

Iahub 为您提供点和线段的所有坐标。请帮他找到什么好的图画。

输入

输入的第一行包含两个整数:n (1 ≤ n ≤ 100) 和 m (1 ≤ m ≤ 100)。下一行包含 n 个空格分隔的整数 x1, x2, ..., xn (0 ≤ xi ≤ 100) — 点的坐标。接下来的m行包含了m个段的描述。每行包含两个整数 li 和 ri (0 ≤ li ≤ ri ≤ 100) — 第 i 段的边界。

保证所有点都是不同的。

输出

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

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

示例

输入 #1

3 3
3 7 14
1 5
6 10
11 15

输出 #1

0 0 0

输入 #2

3 4
1 2 3
1 2
2 3
5 6
2 2

输出 #2

1 0 1