D. Лабораторная работа
ограничение по времени на тест
1 second
ограничение по памяти на тест
256 megabytes
ввод
стандартный ввод
вывод
стандартный вывод

Однажды морж-профессор Платон задал студентам-программистам следующую лабораторную работу.

В лабораторной работе требовалось реализовать такую структуру данных, которая поддерживала бы выпуклую оболочку на некотором множестве точек S. На вход программе подавалось q запросов двух типов:

1. Добавить точку с координатами (x, y) во множество S. Заметьте, что при этом выпуклая оболочка множества S могла измениться, а могла остаться прежней.

2. Сказать, принадлежит ли точка с координатами (x, y) области, ограниченной выпуклой оболочкой, включая границу.

Все студенты справились с заданием. А справитесь ли с ним Вы?

Входные данные

В первой строке содержится целое число q (4 ≤ q ≤ 105).

Далее идут q строк вида "t x y", где t — тип запроса (1 или 2), а (x, y) — координаты точки ( - 106 ≤ x, y ≤ 106, x и y — целые числа).

Гарантируется, что первыми идут 3 запроса первого типа, и точки, данные в этих запросах, образуют невырожденный треугольник. Все точки, добавляемые в S, различны.

Существует хотя бы один запрос второго типа.

Выходные данные

На каждый запрос второго типа выведите по одной строке, содержащей "YES", если точка лежит внутри выпуклой оболочки или на ее границе, и "NO" в противном случае.

Примеры
Входные данные
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