Сама дальня

Задано 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.

Приклади