페이지가 로드되지 않나요? 여기를 눌러보면 고쳐질 수도 있어요.
Placeholder

#4973

Truth Tellers 6s 2048MB

문제

도시에 N명의 사람들이 살고 있다. 이 중 일부는 참말쟁이이고, 나머지는 거짓말쟁이이다.

더욱 구체적으로, 참말쟁이들은 항상 옳은 말만을 하지만, 거짓말쟁이들은 옳은 말이든 거짓말이든 아무 말이나 한다.

모든 사람들에게, 참말쟁이들이 이 도시에 몇 명이 존재하는지 물었다.

그 결과, i번째 사람은 참말쟁이가 A_i명 이상 B_i명 이하라고 대답하였다.

당신이 할 일은 이 증언들을 바탕으로 가능한 참말쟁이의 최대 명수를 구하는 것이다.

그런데, 문제가 발생했다. 사람들의 기억력이 그리 좋지는 못하다는 것이다. 

Q번 증언이 바뀌며, i번째 증언 바뀜에서는 P_i번 사람의 증언이 "참말쟁이가 L_i명 이상, R_i명 이하이다." 로 바뀐다.

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


입력

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

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

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

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


출력

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


예제 

3

0 3

0 3

0 3

6

1 1 2

2 1 2

3 1 2

1 0 0

2 0 0

3 0 0
3 2 2 2 2 1 0
로그인해야 코드를 작성할 수 있어요.