妖精大战争

题目背景

![](https://cdn.luogu.com.cn/upload/pic/4726.png) 琪露诺一如既往忙碌地生活着。 某天,在外出时她的家被人破坏了。 损坏的家插着一面奇怪的旗。 旗上画着似曾相识的几个妖精的图案。 狂怒的琪露诺对旗的主人贴出了宣战告示。 就这样,妖精们的大战争开始了。 (摘自《妖精大战争》manual)

题目描述

三月精Sunny Milk,Lunar Child,Star Sapphire为了让冰之妖精琪露诺加入她们的恶作剧计划,破坏了琪露诺的房子。琪露诺当然不会就此罢休,于是她找到了三月精准备进行复仇,复仇的方式是进行一场弹幕对决。在Normal难度下,Star Sapphire在此次对战中不会出场,因此只有Sunny Milk,Lunar Child两只妖精出场和琪露诺对决了。 在一张符卡中,Sunny Milk和Lunar Child发射的弹幕几乎填满了整个100\*100的正方形战斗场地,并且恰好可以被一条静止不动,非垂直的直线划分成两部分,其中直线上方的部分是Sunny Milk发射的日光弹幕,直线下方的部分是Lunar Child发射的月光弹幕。 琪露诺是最强的妖精,但她面对两只妖精密集的弹幕也会有些紧张。在她的干劲快要被消磨完时,琪露诺忽然发现,如果能用两种不同的策略来对付两种弹幕,获胜的希望将会大大增加。因此,她想知道一些关键的位置会出现什么弹幕。 不幸的是,琪露诺无法判断出分界线在哪里,她只知道当前在战斗场地中每个弹幕的位置,和这个弹幕是月光弹幕还是日光弹幕。在极少情况下(至多0.1%),琪露诺可能会错误识别弹幕的类型,因为它们实在太像了。琪露诺想要了解的是,对于接下来可能出现弹幕的位置,如果出现了弹幕,它是月光弹幕还是日光弹幕。你能帮帮她吗?

输入输出格式

输入格式


第一行三个正整数n,m,k。分别表示当前场地上弹幕的数量,和琪露诺想要了解情况的位置的数量,k表示当前是第几个测试点。 接下来n行,每行两个实数x,y和一个整数k,用空格隔开。表示在(x,y)有一个种类为k的弹幕,k=1为日光弹幕,k=-1为月光弹幕。 接下来m行,每行两个实数x,y,表示琪露诺想知道这个位置如果出现弹幕,会出现什么类型的弹幕。

输出格式


m行,每行一个整数1或者-1,对应每个询问的结果。 1为日光弹幕,-1为月光弹幕。

输入输出样例

输入样例 #1

4 4
3.000 4.000 1
3.000 3.000 -1
8.000 3.000 -1
8.000 4.000 1
100.000 100.000
0.000 0.000
3.141 5.926
0.618 1.618

输出样例 #1

1
-1
1
-1

说明

样例解释: 注:该数据因量过小,信息量不足而不合法,可能会发生无法得到准确答案的情况。因此仅供理解题意使用,不可用来测试程序。 观察输入数据,我们发现当y=3时,都是月光弹幕,y=4时,都是日光弹幕。可以猜想直线在y=3~y=4之间。 因此对于四个询问分别回答 1,-1,1,-1 数据范围和提示 单个弹幕的面积可视为0。 若询问的位置恰好落在分界线上,当做在分界线的下方处理。 本题有SpecialJudge。 对于第1个测试点 N=100000,m=100000 若你输出的答案中,正确回答的询问数量大于等于总询问数量的30%,则可以获得该测试点的全部分数,否则得0分。 对于第2~5个测试点, n=1000,m=1000 若你输出的答案中,正确回答的询问数量大于等于总询问数量的60%,则可以获得该测试点的全部分数,否则得0分。 对于第6~7个测试点, n=100000,m=100000 若你输出的答案中,正确回答的询问数量大于等于总询问数量的70%,则可以获得该测试点的全部分数,否则得0分。 对于第8~10个测试点, n=100000,m=100000 若你输出的答案中,正确回答的询问数量大于等于总询问数量的80%,则可以获得该测试点的全部分数,否则得0分。 对于100%的数据 0.000<=x,y<=100.000 所有输入的实数均保留3位小数。 保证输入数据有合法的解能够满足题目要求的判定准确率。 评测时限:对于测试点2~5,时限为1s,其他测试点时限为2s