eolymp
bolt
Попробуйте наш новый интерфейс для отправки задач
Задачи

Самая дальняя

Самая дальняя

Лимит времени 2 секунды
Лимит использования памяти 256 MiB

Даны N точек на плоскости, нужно уметь обрабатывать следующие запросы:

  • get a b — возвращает максимум по всем точкам величины ax + by.

  • add x y — добавить точку в множество.

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

Число N (1N10^5) и N точек. Далее число M (1M10^5) — количество запросов и собственно запросы. Формат запросов можно посмотреть в примере. Все координаты точек и числа a, b — целые числа, по модулю не превосходящие 10^9.

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

На каждый запрос вида get выведите одно целое число — максимум величины 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