eolymp
bolt
Try our new interface for solving problems
Problems

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

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

Time limit 2 seconds
Memory limit 256 MiB

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

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

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

Input data

Число N (1N10^5) и N точек. Далее число M (1M10^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