题目描述

FJ 需要你帮助他决定在哪里建造形状是一条无限长的直线的栅栏来限制他的牛的活动。他选出了几个可能的建造栅栏的位置，你需要帮助他判断哪些栅栏是有用的。

一个栅栏是有用的当且仅当所有奶牛都在栅栏的同一侧（如果有牛群在栅栏所在的直线上，那么栅栏是没用的），FJ 将会问你一些问题，如果这个栅栏是有用的，需要输出 YES，反之输出 NO。 另外，FJ 也可能会带来一些新的奶牛加入这个牛群。一头牛加入之后，以后的所有询问中，这头牛也需要与其它的牛在栅栏的同一侧。

输入格式

第一行包含两个用空格隔开的整数 $N$ 和 $Q$，代表最开始奶牛的数目和 FJ 的提问的个数。

接下来的 $N$ 行，每行包含两个整数 $x$ 和 $y$，代表每只奶牛的坐标。

最后的 $Q$ 行，每行代表一个提问：

• 形如 1 x y 的提问代表 FJ 在坐标为 $(x,y)$ 的位置放置了一头新的奶牛；
• 形如 2 A B C 的提问代表 FJ 向你询问位于直线 $Ax+By=C$ 上的栅栏是否是有用的。

输出格式

对于每个形如 2 A B C 的提问，输出一行，如果栅栏有用则输出 YES，否则输出 NO。

3 4
0 0
0 1
1 0
2 2 2 3
1 1 1
2 2 2 3
2 0 1 1

YES
NO
NO

样例解释

最开始的三头牛都在 $2x+2y=3$ 这条直线同侧，但是奶牛 $(1,1)$ 加入后，与其它三头牛不在同一侧，所有第二个栅栏是没用的。

因为奶牛 $(0,1)$ 和奶牛 $(1,1)$ 在直线 $y=1$ 上，所以第三个栅栏是没用的。

数据范围与提示

对于 $100\%$ 的数据，有 $1\le N,Q\le 10^5$，$-10^9\le x,y,A,B\le 10^9$，$-10^{18}\le C\le 10^{18}$，保证牛之间两两不重合，且不存在满足 $A=B=0$ 的询问。

题目来源

USACO February 2015 Contest Gold T3