Дано \(N\) прямих виду \(y=kx+b\)

Необхідно обробляти 2 типи запитів:
1) Добавити пряму виду \(y=kx+b\) в набір
2) Для заданого \(x\) знайти найменше значення \(y\) серед усіх прямих з набору

ДОДАТКОВІ УМОВИ:

• Всі прямі задані в довільному порядку
• Всі \(x\) задані в довільному порядку

Формат вхідних даних

В першому рядку два цілі числа \(N,Q\) - кількість початкових прямих та кілкьість запитів. (\(1<=N,Q <= 200000\))
В наступних \(N\) рядках містяться по два ццлих числа \(k,b\) - оефіцієнти кожної прямої.
В наступних \(Q\) рядках містяться запити.

0 k b - позначає перший тип запиту
1 x - позначає другий тип запиту
\(-10^9 \le k,x \le 10^9\) , \(-10^{18} \le b \le 10^{18}\)

Формат вихідних даних

Для кожного запиту типу 2 виведіть відповідь в окремому рядку.

Приклад вхідних даних

2 8
-1 -1
0 1
1 -1
1 -2
1 0
1 2
0 0 -10
1 -2
1 0
1 2

Приклад вихідних даних

0
1
-1
-3
-10
-10
-10