Migrated from Lutece 2548 小兔又养马

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

小兔的农场上养了许多马，这些马正在不同的位置吃草。现在小兔想修建栅栏，把所有的马圈养起来。

我们可以把农场看作一个二维坐标平面，把马看作平面上的不同点。由于小兔很缺钱，他现在只买来了一条栅栏，但是这条栅栏巨(TM)长，可以看作平面上的一条直线。

小兔在放置栅栏时发现了一个问题：栅栏并不可以随意放置。具体地来说，小兔不希望栅栏把他养的马隔开，栅栏也不可以穿过马所在的位置。

现在小兔有若干放置这条栅栏的方案，请你回答小兔这些方案是否可行，即所有的马是否在这条栅栏的同一侧。由于马的繁殖能力很强，在询问过程中可能会在某一位置诞生新的马。

Input

第一行两个整数 $n$ 和 $q$ ($1\le n,q \le 10^5$)，表示初始时马的个数，以及询问次数。

接下来 $n$ 行，每行两个整数 $x,y$ ($-10^9 \le x,y \le 10^9$)，表示一匹马的位置为 $(x,y)$。

接下来 $q$ 行，每行表示一个询问或在某一位置诞生新的马。

• 1 x y 表示在 $(x,y)$ 诞生一匹新的马 ($-10^9 \le x,y \le 10^9$)。
• 2 A B C 表示询问所有的马是否在直线 $Ax+By=C$ 的同一侧 ($-10^9 \le A,B \le 10^9, -10^{18} \le C \le 10^{18}$)，数据保证不会出现 $A=B=0$。

Output

对于每次询问，输出所有的马是否在栅栏的同一侧。如果是，输出 YES；否则，输出 NO。

Samples

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

Resources

2021 UESTC ICPC Training for Math and Geometry