Problem: Once a walrus professor Plato asked his programming students to perform the following practical task. 

The students had to implement such a data structure that would support a convex hull on some set of points S. The input to the program had q queries of two types: 

1. Add a point with coordinates (x, y) into the set S. Note that in this case the convex hull of S could have changed, and could have remained the same. 

2. Say whether a point with coordinates (x, y) belongs to an area limited by the convex hull, including the border. 

All the students coped with the task. What about you?

Input

The first line contains an integer q (4 ≤ q ≤ 105). 

Then follow q lines in the following way: "t x y", where t is the query type (1 or 2), and (x, y) are the coordinates of the point ( - 106 ≤ x, y ≤ 106, x and y are integers). 

There is at least one query of type 2.

It is guaranteed that the three queries of the first type follow first and the points given in the queries form a non-degenerative triangle. Also all the points added in S are distinct.

Output

For each query of the second type print one string containing "YES", if the point lies inside the convex hull or on its border. Otherwise, print "NO".

Examples

Input

8
1 0 0
1 2 0
1 2 2
2 1 0
1 0 2
2 1 1
2 2 1
2 20 -1


Output

YES
YES
YES
NO

Solution (in JAVA):

Solution:
import java.io.*;
import java.util.*;

public class Task {
    
    BufferedReader br;
    StringTokenizer st;
    boolean eof;
    
    public static void main(String[] args) throws IOException{
        new Task();
    }
    
    public final double EPS = 1e-12;
    
    class Point {
        double x, y;
        Point(double x, double y) {
            this.x = x; this.y = y;
        }
    }
    Point O;
    double angle(Point a, Point b) {
        if(a.x == b.x && a.y == b.y) return Math.PI;
        return Math.atan2(b.y - a.y, b.x - a.x);
    }
    double angleO(Point a) {
        return angle(O, a);
    }
    boolean ccw(Point A, Point B, Point C) {
        double x0 = B.x - A.x, y0 = B.y - A.y, x1 = C.x - A.x, y1 = C.y - A.y;
        return x0 * y1 - x1 * y0 > EPS;
    }
    boolean ccwOrColl(Point A, Point B, Point C) {
        double x0 = B.x - A.x, y0 = B.y - A.y, x1 = C.x - A.x, y1 = C.y - A.y;
        return x0 * y1 - x1 * y0 > -EPS;
    }
    
    public Task() throws IOException{
        br = new BufferedReader(new InputStreamReader(System.in));
        //PrintStream out = System.out;
        PrintWriter out = new PrintWriter(System.out);
        int nq = nextInt();
        TreeSet<Point> hull = null;
        
        //ArrayList<Point> pts = new ArrayList<>();
        double[] x3 = new double[3], y3 = new double[3];
        for(int k = 0; k < 3; k++) {
            nextInt(); x3[k] = nextDouble(); y3[k] = nextDouble();
        }
        O = new Point(x3[0] / 2 + (x3[1] + x3[2]) / 4, y3[0] / 2 + (y3[1] + y3[2]) / 4);
        hull = new TreeSet<>(new Comparator<Point>(){
            @Override
            public int compare(Point a, Point b) {
                double alpha = angleO(a) - angleO(b);
                return alpha < -EPS ? -1 : (alpha > EPS? 1 : 0);
            }
        });
        for(int k = 0; k < 3; k++)
            hull.add(new Point(x3[k], y3[k]));
        nq -= 3;
        
        while(nq-- > 0) {
            int type = nextInt();
            double x = nextDouble(), y = nextDouble();
            
            if(type == 2) {
                out.println(processQuery(hull, new Point(x, y), type)? "YES" : "NO");
            }
            else if(type == 1) {
                //pts.add(new Point(x, y));
                processQuery(hull, new Point(x, y), type);
            }
            //out.println("checking... " + convexHullCheck(pts, hull));
        }
        
        
        /*do not touch**/
        out.close();
    }
    boolean inBoundingBox(Point P, Point A, Point B, Point C) {
        double maxx = Math.max(C.x, Math.max(A.x, B.x));
        double maxy = Math.max(Math.max(A.y, B.y), C.y);
        double minx = Math.min(C.x, Math.min(A.x, B.x));
        double miny = Math.min(Math.min(A.y, B.y), C.y);
        return P.x - minx > -EPS && P.x - maxx < EPS && P.y - maxy < EPS && P.y - miny > -EPS;
    }
    boolean inTriangle(Point P, Point A, Point B, Point C) { ///ccw A, B, C = true
        if(!inBoundingBox(P, A, B, C)) return false;
        return ccwOrColl(A, B, P) && ccwOrColl(B, C, P) && ccwOrColl(C, A, P);
    }
    
    boolean processQuery(TreeSet<Point> hull, Point A, int type) {
        Point prev, next;
        next = hull.ceiling(A);
        if(next == null)
            next = hull.first();
        prev = hull.lower(A);
        if(prev == null)
            prev = hull.last();
        if(inTriangle(A, prev, next, O)) {
            if(type == 2)
                return true;
            return false;
        }
        else if(type == 1)
            insertInCH(hull, A, next);
        return false;
    }
    void insertInCH(TreeSet<Point> hull, Point A, Point nxt) {
        Point next1, next2; 
        next1 = nxt;
        next2 = hull.higher(next1);
        if(next2 == null) 
            next2 = hull.first();
        while(!ccw(A, next1, next2)) {
            hull.remove(next1);
            next1 = next2;
            next2 = hull.higher(next1);
            if(next2 == null) 
                next2 = hull.first();
        }
        //remove nexts cw
        next1 = hull.floor(A);
        if(next1 == null)
            next1 = hull.last();
        next2 = hull.lower(next1);
        if(next2 == null)
            next2 = hull.last();
        while(!ccw(A, next2, next1)) {
            hull.remove(next1);
            next1 = next2;
            next2 = hull.lower(next1);
            if(next2 == null)
                next2 = hull.last();
        }
        hull.add(A);
    }
    
    boolean convexHullCheck(ArrayList<Point> points, TreeSet<Point> hull) {
        if(points.size() < 4) return true;
        Collections.sort(points, (p, q) ->(p.x < q.x? -1 : 1));
        ArrayList<Point> ch = new ArrayList<>();
        ch.add(points.get(0));
        for(int i = 1; i <= points.size(); i++) {
            while(ch.size() > 1) {
                while(!ccw(points.get(i), ch.get(ch.size() - 2), ch.get(ch.size() - 1)))
                    ch.remove(ch.size() - 1);
            }
            ch.add(points.get(i));
        }
        for(int i = points.size() - 1; i >= 1; i--) {
            while(!ccw(points.get(i), ch.get(ch.size() - 2), ch.get(ch.size() - 1)))
                ch.remove(ch.size() - 1);
            ch.add(points.get(i));
        }
        for(int i = 0; i < ch.size(); i++) {
            if(hull.contains(ch.get(i)) == false)
                return false;
        }
        return true;
    }
    
    
    /*reading stuff*/
    String nextToken() {
        while (st == null || !st.hasMoreTokens()) {
            try {
                st = new StringTokenizer(br.readLine());
            } catch (Exception e) {
                eof = true;
                return null;
            }
        }
        return st.nextToken();
    }

    int nextInt() throws IOException {
        return Integer.parseInt(nextToken());
    }

    long nextLong() throws IOException {
        return Long.parseLong(nextToken());
    }

    double nextDouble() throws IOException {
        return Double.parseDouble(nextToken());
    }
}