На площині існує множина \(S\) точок. \(S\) спочатку порожня.

Для кожного \(i = 1, 2, \dots, Q\) у цьому порядку обробіть наступний запит.

• Вам задано цілі числа \(X_i, Y_i, A_i, B_i\). Додайте точку (\(X_i, Y_i\)) до \(S\), а потім знайдіть \(\displaystyle \max_{(x,y) \in S}\left\{A_ix + B_iy\right\}\).

Обмеження

• Усі значення у вхідних даних є цілими числами.

• \(1 ≤ Q ≤ 2 \times 10^5\)

• \(|X_i|, |Y_i|, |A_i|, |B_i| ≤ 10^9\)

• Якщо i ≠ j, тоді \((X_i, Y_i) ≠ (X_j, Y_j)\).

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

Перший рядок містить ціле число \(Q\)

Наступні  \(Q\) рядків містять цілі числа \(X_i, Y_i, A_i, B_i\)

Числа у рядках розділяються пропуском.

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

У вихідний потік виведіть в окремих рядках відповідь на кожен із запитів.

Примітка

До прикладу 1:

• Коли i = 1: додайте точку (1, 0) до S, тоді вона стане S = {(1, 0)}. Для (x, y) = (1, 0), ми маємо -x - y = -1, що є максимумом.

• Коли i = 2: додайте точку (0, 1) до S, тоді вона стане S = {(0, 1), (1, 0)}. Для (x, y) = (1, 0), ми маємо 2x = 2, що є максимумом.

• Коли i = 3: додайте точку (-1, 0) до S, тоді вона стане S = {(-1, 0), (0, 1), (1, 0) }. Для (x, y) = (1, 0) або (x, y) = (0, 1), ми маємо x + y = 1, що є максимумом.

• Коли i = 4: додайте точку (0, -1) до S, тоді вона стане S = {(-1, 0), (0, -1), (0, 1 ), (1, 0)}. Для (x, y) = (0, -1) ми маємо x - 2y = 2, що є максимумом.

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

4
1 0 -1 -1
0 1 2 0
-1 0 1 1
0 -1 1 -2

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

-1
2
1
2

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

9
-1 4 -8 -2
9 -9 -7 7
4 1 6 7
-4 -1 -4 -5
-9 3 -2 -6
-1 0 -8 5
-8 -5 0 0
8 3 0 -4
2 -5 2 5

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

0
35
31
21
36
87
0
36
31