Задачі
Сама дальня
Сама дальня
Задано \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