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

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

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

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

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

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

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

На каждый запрос вида get выведите одно целое число — максимум величины ax + by.

Примеры