진실을 말하는 사람

도시에 $N$명의 사람들이 살고 있다. 이 중 일부는 참말쟁이이고, 나머지는 거짓말쟁이이다. 참말쟁이들은 항상 옳은 말만 하지만, 거짓말쟁이들은 옳은 말이든 거짓말이든 아무 말이나 한다.

모든 사람들에게 참말쟁이가 이 도시에 몇 명 있는지 물었다. $i$번째 사람은 참말쟁이가 $A_i$명 이상 $B_i$명 이하라고 대답하였다. 이 증언들을 바탕으로 가능한 참말쟁이의 최대 명수를 구하여라.

그런데 문제가 생겼다. 사람들의 기억력이 그리 좋지 않다. $Q$번 한 사람의 증언이 바뀌며, $i$번째로 증언이 바뀔 때에는 $P_i$번 사람의 증언이 "참말쟁이가 $L_i$명 이상, $R_i$명 이하이다."로 바뀐다.

초기 상태를 포함한 $Q+1$번의 상황 각각에 대해 참말쟁이의 최대 명수를 구하여라.

첫 줄에 $N$이 주어진다. ($1 \le N \le 5 \times 10^5$)

$N$개의 줄에 걸쳐 $A_i$와 $B_i$가 순서대로 주어진다. ($0 \le A_i \le B_i \le N$)

다음 줄에 $Q$가 주어진다. ($1 \le Q \le 5 \times 10^5$)

$Q$개의 줄에 걸쳐 $P_i$, $L_i$, $R_i$가 순서대로 주어진다. ($1 \le P_i \le N$, $0 \le L_i \le R_i \le N$)

$Q+1$번의 상황 각각에 대해 참말쟁이의 최대 명수를 공백으로 구분하여 순서대로 한 줄에 출력한다.