Description

Farmer John needs your help deciding where to build a fence in the shape of a straight line to help restrict the movement of his cows.

He has considered several possible fence locations and needs your help to determine which of these are usable, where a fence is considered usable if all of the cows are on the same side of the fence. A fence is not usable if there is a cow that lies directly on it.

FJ will be asking you a number of queries regarding possible fence locations; a query should be answered YES if it corresponds to a usable fence location, NO otherwise.

Additionally, FJ may occasionally bring new cows into the herd. When a new cow joins the herd, all fence queries from that point onward will require her to be on the same side of a fence as the rest of the herd for the fence to be usable.

Input Format

The first line of input contains $N$ and $Q$ separated by a space. These give the number of cows initially in the herd and the number of queries, respectively.

The following $N$ lines describe the initial state of the herd. Each line will contain two space separated integers $x$ and $y$ giving the position of a cow.

The remaining $Q$ lines contain queries either adding a new cow to the herd or testing a fence for usability.

• A line of the form 1 x y means that a new cow has been added to the herd at position $(x, y)$.
• A line of the form 2 A B C indicates that FJ would like to test a fence described by the line $Ax + By = C$.

Output Format

For each fence query, output YES if the fence is usable. Otherwise output 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

Limit and Hint

For $100\%$ of testcases, $1\le N,Q\le 10^5$, $-10^9\le x,y,A,B\le 10^9$, $-10^{18}\le C\le 10^{18}$, all cow positions will be unique over the whole data set, and no fence query will have $A=B=0$.

Source

USACO February 2015 Contest Gold T3