Truth Tellers

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

모든 사람들에게, 참말쟁이들이 이 도시에 몇 명이 존재하는지 물었다. 그 결과, i번째 사람은 참말쟁이가 Ai명 이상 Bi명 이하라고 대답하였다. 당신이 할 일은 이 증언들을 바탕으로 가능한 참말쟁이의 최대 명수를 구하는 것이다.

그런데, 문제가 발생했다. 사람들의 기억력이 그리 좋지는 못하다는 것이다. Q번 한 사람의 증언이 바뀌며, i번째 증언 바뀜에서는 Pi번 사람의 증언이 "참말쟁이가 Li명 이상, Ri명 이하이다." 로 바뀐다.

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

첫 줄에 N이 주어진다. (1 ≤ N ≤ 5×105)

N개의 줄에 걸쳐, Ai와 Bi가 순서대로 주어진다. (0 ≤ Ai ≤ Bi ≤ N)

다음 줄에 Q가 주어진다. (1 ≤ Q ≤ 5×105)

Q개의 줄에 걸쳐, Pi, Li, Ri가 순서대로 주어진다. (1 ≤ Pi ≤ N, 0 ≤ Li ≤ Ri ≤ N)

Q+1개의 경우의 참말쟁이의 최대 명수를 공백으로 구분하여 순서대로 한 줄에 출력한다.