23751번 - 던전 릴레이

선호는 RPG 게임을 즐긴다. 이 RPG 게임에서는 지불 또는 보상 수단으로 캐시라는 재화를 사용한다. 

이 게임에는 $1$번부터 $N$번까지의 던전이 있으며, 각 던전마다 입장하려면 지불해야 할 캐시 금액인 입장료가 필요하고 던전을 깨면 보상으로 받는 캐시 금액이 있다. 또한 각 던전마다 플레이 난이도가 있지만, 서버 랭킹 1위인 선호의 캐릭터는 워낙 강해서 던전에 입장만 가능하면 난이도와 상관없이 입장한 던전을 깰 수 있다.

이 게임에는 던전 릴레이라는 시스템이 있는데, 사냥할 던전의 난이도 범위를 설정하면 이 범위 안에 있는 난이도의 모든 던전을 사냥하는 것이다. 이때, 캐릭터는 난이도 범위에 속하면서 난이도가 가장 낮은 던전부터 가장 높은 던전까지 오름차순으로 던전을 깨야 하고, 난이도가 같은 던전이 있으면 던전 번호의 오름차순으로 던전을 깨야 한다. 즉, 설정한 난이도 범위에 있는 모든 던전을 규칙에 따라 차례대로 깨야 릴레이를 성공적으로 마칠 수 있다. 그런데 릴레이 도중 어떤 한 던전에 입장할 때 가지고 있는 캐시 금액이 입장료보다 적으면 그 던전에 입장이 불가해서 플레이 중인 릴레이가 중단된다.

던전 릴레이 도중에 깬 던전은 해당 릴레이를 진행하는 동안에는 재입장이 불가하지만, 이후의 던전 릴레이에서는 입장료만 낼 수 있으면 다시 입장이 가능하여 깰 수 있다. 또한 보상으로 받는 캐시 금액은 각 던전을 깨는 즉시 지급된다.

참가할 던전 릴레이의 난이도 범위가 주어졌을 때 선호가 해당 릴레이를 성공적으로 마칠 수 있을지를 알려주자.

첫 번째 줄에는 던전의 수 $N$이 주어진다. ($1 \le N \le 10^5$)

두 번째 줄부터 $N$개의 줄에 걸쳐 $1$번부터 $N$번까지 차례대로 각 던전의 난이도 $d_i$ , 입장료 캐시 금액 $e_i$, 던전을 깬 후 받을 수 있는 보상 캐시 금액 $f_i$가 정수로 주어진다. ($1 \le d_i \le 10^9$, $0 \le e_i, f_i \le 10^9$, $1 \le i \le N$)

$N + 2$ 번째 줄에는 쿼리의 수 $Q$가 주어진다. ($1 \le Q \le 10^5$)

$N + 3$ 번째 줄부터 $Q$개의 줄에 걸쳐 쿼리가 한 줄에 하나씩 주어진다. 이때, 쿼리는 아래 형식 중 하나를 따르며, 모든 변수는 정수임이 보장된다.

• 1 c l r: 선호의 캐릭터가 릴레이 시작 전 $c$만큼의 캐시 금액을 가진 상태에서 난이도 범위가 $l$ 이상 $r$ 이하인 던전 릴레이를 성공적으로 마칠 수 있으면 $1$을, 플레이 도중 중단되거나 주어진 난이도 범위를 만족하는 던전이 존재하지 않으면 $-1$을 출력한다. 성공적으로 마칠 수 있으면 해당 던전 릴레이를 끝낸 후 선호가 가지고 있을 캐시 금액을 같은 줄에 공백을 두고 출력한다. ($0 \le c \le 10^9$, $1 \le l \le r \le 10^9$)
• 2 x v: $x$번 던전의 입장료를 $v$로 바꾼다. ($1 \le x \le N$, $0 \le v \le 10^9$)
• 3 x v: $x$번 던전의 보상 캐시 금액을 $v$로 바꾼다. ($1 \le x \le N$, $0 \le v \le 10^9$)

$1$로 시작하는 쿼리들에 대해, 정답을 한 줄에 하나씩 순서대로 출력한다.