Problems
Самая дальняя
Самая дальняя
Даны N точек на плоскости, нужно уметь обрабатывать следующие запросы:
get a b — возвращает максимум по всем точкам величины ax + by.
add x y — добавить точку в множество.
Input data
Число N (1 ≤ N ≤ 10^5) и N точек. Далее число M (1 ≤ M ≤ 10^5) — количество запросов и собственно запросы. Формат запросов можно посмотреть в примере. Все координаты точек и числа a, b — целые числа, по модулю не превосходящие 10^9.
Output data
На каждый запрос вида get выведите одно целое число — максимум величины ax + by.
Examples
Input example #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
Output example #1
1 0 1 1 4 4 1 1