logo AlgoBeat OnlineJudge
登录 注册

#215902. [蓝桥杯第一届国际赛] 平面染色

内存限制:512 MiB 时间限制:5000 ms 标准输入输出
题目类型:VJudge(洛谷) 评测方式:VJudge
上传者: 匿名

题目描述

小 C 有一张很大的白纸(假定无限大)。闲暇之余,小 C 喜欢在纸上用直线画出各种图案,这些直线将白纸分割成为若干区域。小 C 想用黑白两种颜色填充每一个区域。若两个区域有公共边,则它们是相邻的。若相邻的两个区域填充了同一种颜色,这种方案就十分不美观。并且小 C 希望白纸的中心保留原有的白色,即原点所在区域是白色的。

现在小 C 已经画好了这 条直线,但是分割出的区域太多了,他找不出一个美观的染色方案。现在小 C 希望机智的你可以告诉他一种染色方案。小 C 会向你询问纸上 个点的颜色,以帮助他了解染色情况。

若染色方案不唯一,你只需给出一种就可以了。

输入格式

输入一行,包含两个正整数 ,分别表示直线的数量和询问的点数。

接下来 行,每行包含 个整数 ,表示一条过点 和点 的直线。

接下来 行,每行包含 个整数 ,表示询问点 的颜色。

输出格式

若不存在一种美观的染色方案,则输出

若存在一种美观的染色方案,则输出 行,每行包含一个数字(),表示在你给出的这种染色方案中,询问点的颜色( 表示黑, 表示白)。

样例

样例输入 1

3 3
-1 -1 1 2
1 2 2 0
2 0 -1 -1
0 0
2 -1
1 3

样例输出 1

1
0
1

数据范围与提示

评测用例规模与约定

对于 的评测用例,,保证每条直线必与坐标轴平行;

对于 的评测用例,,保证每条直线必与坐标轴平行;

对于另外 的评测用例,

对于所有评测用例,

对于所有评测用例,保证点 与点 不相同,保证给出的直线两两不同,保证 不在任何一条给定直线上,保证原点不在任何一条给定直线上。