Bao lồi

Giáo sư hải mã Plato đã giao cho các sinh viên lập trình của mình thực hiện một bài tập thực hành sau:

Các sinh viên phải xây dựng một cấu trúc dữ liệu hỗ trợ việc quản lý Bao lồi (Convex Hull) trên một tập hợp điểm \(S\) cho trước. Chương trình nhận \(q\) truy vấn thuộc hai loại:

• Thêm điểm: Thêm một điểm với tọa độ \((x, y)\) vào tập hợp \(S\). Lưu ý rằng trong trường hợp này, bao lồi của \(S\) có thể thay đổi hoặc giữ nguyên.
• Kiểm tra: Xác định xem một điểm với tọa độ \((x, y)\) có thuộc khu vực được giới hạn bởi bao lồi hay không, bao gồm cả biên (đường bao).

Tất cả các sinh viên đều hoàn thành nhiệm vụ. Còn bạn thì sao?

Input

• Dòng đầu tiên chứa một số nguyên \(q\) (\(4 \le q \le 10^5\)) --- số lượng truy vấn.
• Sau đó là \(q\) dòng theo định dạng: "\(t\) \(x\) \(y\)", trong đó \(t\) là loại truy vấn (1 hoặc 2), và \((x, y)\) là tọa độ của điểm (\(-10^6 \le x, y \le 10^6\), \(x\) và \(y\) là các số nguyên).

Output

Với mỗi truy vấn loại 2, in ra một chuỗi chứa "YES", nếu điểm nằm bên trong bao lồi hoặc trên biên của nó. Ngược lại, in ra "NO".

Example

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

YES
YES
YES
NO

Scoring

• Subtask \(1\) (\(40\%\) số điểm) : \(q \leq 500\).
• Subtask \(2\) (\(30\%\) số điểm) : các thao tác loại \(1\) luôn xuất hiện trước các thao tác loại \(2\).
• Subtask \(3\) (\(30\%\) số điểm) : không có ràng buộc gì thêm.