Задачи
Самая дальняя
Самая дальняя
Даны \textbf{N} точек на плоскости, нужно уметь обрабатывать следующие запросы:
\begin{itemize}
\item \textbf{get a b} --- возвращает максимум по всем точкам величины \textbf{ax + by}.
\item \textbf{add x y} --- добавить точку в множество.
\end{itemize}
\InputFile
Число \textbf{N} (\textbf{1} ≤ \textbf{N} ≤ \textbf{10^5}) и \textbf{N} точек. Далее число \textbf{M} (\textbf{1} ≤ \textbf{M} ≤ \textbf{10^5}) --- количество запросов и собственно запросы. Формат запросов можно посмотреть в примере. Все координаты точек и числа \textbf{a}, \textbf{b} --- целые числа, по модулю не превосходящие \textbf{10^9}.
\OutputFile
На каждый запрос вида \textbf{get} выведите одно целое число --- максимум величины \textbf{ax + by}.
Входные данные #1
3 0 0 1 0 0 1 10 get 1 1 get -1 -1 get 1 -1 get -1 1 add 2 2 add -2 -2 get 1 1 get -1 -1 get 1 -1 get -1 1
Выходные данные #1
1 0 1 1 4 4 1 1