Tý cần giải bài toán sau:

Mot cong ty san xuat muon toi da hoa loi nhuan tu mot day chuyen san xuat. Moi each van hanh duoc mo ta bang mot duong thang \(y = a \cdot x + b\), the hien loi nhuan theo san luong \(x\).

Co \(Q\) thao tac:

• Them mot phuong an san xuat moi \(y = a \cdot x + b\).
• Voi san luong \(x\) cho truoc, hay tinh loi nhuan lon nhat co the dat duoc.

Dinh dang dau vao

• Dong dau tien chua so nguyen \(Q\) (\(1 \le Q \le 10^5\)).
• \(Q\) dong tiep theo:
  • \(1\) \(a\) \(b\): Them duong thang \(y = a \cdot x + b\) (\(|a|, |b| \le 10^9\)).
  • \(2\) \(x\): Truy van gia tri lon nhat tai \(x\) (\(|x| \le 10^9\)).

Dinh dang dau ra

• Voi moi truy van loai \(2\), in ra mot so nguyen.

Vi du

Input:

7
1 2 1
1 -1 10
2 3
2 0
1 0 3
2 5
2 -2

Output:

10
10
13
17

Giai thich: Tai \(x=3\): \(\max(2\times 3+1=7, -3+10=7) = 7\). Tai \(x=0\): \(\max(1, 10) = 10\). Them \(y=3\) (id=3). Tai \(x=5\): \(\max(11, 5, 3)=11\). Tai \(x=-2\): \(\max(-3, 12, 3)=12\).

Rang buoc

• Subtask 1 (20%): \(Q \le 200\).
• Subtask 2 (30%): \(Q \le 5000\).
• Subtask 3 (50%): \(Q \le 10^5\).