P3691 妖精大战争

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

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

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

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

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