직선과 구간 직선의 최솟값

처음에 비어 있는 직선 집합 $S$가 있다. 각 직선에는 기울기 $a$, 절편 $b$와 유효 구간이 정해져 있다. 다음 $Q$개의 쿼리를 순서대로 처리해 보자.

• $1\ a\ b$: 모든 실수 $x$에서 유효한 직선 $y=ax+b$를 $S$에 추가한다.
• $2\ l\ r\ a\ b$: $l \le x \le r$에서만 유효한 직선 $y=ax+b$를 $S$에 추가한다.
• $3\ x$: $x$에서 유효한 직선들의 $ax+b$ 중 최솟값을 구한다.

같은 직선을 여러 번 추가할 수 있다. 질의한 위치에서 유효한 직선이 없을 수도 있다.

첫 번째 줄에 정수 $Q$가 주어진다. $(1 \le Q \le 200\,000)$

두 번째 줄부터 $Q$개의 줄에 걸쳐 쿼리가 주어진다. 각 쿼리는 본문에 설명된 형식으로 주어지며, 한 줄의 값은 공백으로 구분되어 주어진다.

$1$번 쿼리에는 두 정수 $a$, $b$가 공백으로 구분되어 주어진다. $(-10^9 \le a \le 10^9; -10^{18} \le b \le 10^{18})$

$2$번 쿼리에는 네 정수 $l$, $r$, $a$, $b$가 공백으로 구분되어 주어진다. $(-10^9 \le l \le r \le 10^9; -10^9 \le a \le 10^9; -10^{18} \le b \le 10^{18})$

$3$번 쿼리에는 정수 $x$가 주어진다. $(-10^9 \le x \le 10^9)$

$3$번 쿼리의 답을 쿼리가 주어진 순서대로 한 줄에 하나씩 출력한다. 해당 $x$에서 유효한 직선이 없다면 EMPTY를 출력한다.