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

Cong ty vien thong XYZ co mot mang luoi truyen dan voi \(Q\) thao tac. Moi thiet bi hoat dong trong mot pham vi tan so nhat dinh. Khi lap dat thiet bi moi, cuong do tin hieu cua no duoc mo ta bang mot ham tuyen tinh \(y = a \cdot x + b\), nhung chi co hieu luc trong khoang tan so \([L, R]\).

Nhan vien ky thuat can kiem tra cuong do tin hieu tai mot tan so bat ky de dam bao chat luong dich vu.

Cu the, co \(Q\) thao tac:

• Them mot thiet bi trong doan \([L, R]\) voi ham tin hieu \(y = a \cdot x + b\).
• Kiem tra cuong do tin hieu nho nhat tai tan so \(x\).

Dinh dang dau vao

• Dong dau tien chua so nguyen \(Q\) (\(1 \le Q \le 10^5\)).
• \(Q\) dong tiep theo, moi dong co mot trong hai dang:
  • \(1\) \(L\) \(R\) \(a\) \(b\): Them doan thang \(y = a \cdot x + b\) tren \([L, R]\) (\(|a|, |b| \le 10^9, 1 \le L \le R \le 10^9\)).
  • \(2\) \(x\): Truy van gia tri nho nhat tai \(x\) (\(1 \le x \le 10^9\)).

Dinh dang dau ra

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

Vi du

Input:

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

Output:

7
7
5
7

Giai thich: Doan \(y=2x+3\) hieu luc tren \([1,5]\), doan \(y=-x+10\) tren \([2,8]\). Tai \(x=3\): \(\min(9, 7) = 7\). Tai \(x=5\): \(\min(13, 5) = 5\).

Rang buoc

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