쿠키 공장

유민이의 쿠키 공장에 $N$개의 회사로부터 수주가 들어왔다. $i$번째 회사에는 총 $c_i$박스의 쿠키를 공급해야 하며, $s_i$일차부터 납품을 시작할 수 있다.

공장에서는 $x$일차에 다음 두 행동 중 하나를 선택한다.

• $s_i \leq x$를 만족하는 $i$를 선택한 뒤, 1박스의 쿠키를 만들어 $i$번째 회사에 공급한다.
• 쿠키 대신 사내 리듬게임 대회를 개최한다.

쿠키는 미리 만들어 다른 날에 공급할 수 없다. 만든 쿠키는 반드시 당일에 공급해야 한다. 모든 회사에 납품을 마치기 위해 마지막으로 쿠키를 만드는 날이 최소 몇 일차인지 계산하자.

쿠키 산업은 앞일을 예측하기 어려워서 수주 조건 수정 요청이 $Q$건 들어왔다. $j$번째 수정 요청에서는 $q_j$번째 회사에 공급할 쿠키를 $c'_j$박스로, 공급 시작 일차를 $s'_j$일차로 바꾼다. 각 수정은 초기화되지 않고 이후 요청의 처리에도 계속 반영된다. 시작 상태와 각 수정 요청 이후의 정답을 구하자.

첫 번째 줄에 정수 $N$이 주어진다.

다음 $N$개의 줄 중 $i$번째 줄에 두 정수 $c_i$, $s_i$가 공백으로 구분되어 주어진다.

다음 줄에 정수 $Q$가 주어진다.

다음 $Q$개의 줄 중 $j$번째 줄에 세 정수 $q_j$, $c'_j$, $s'_j$가 공백으로 구분되어 주어진다.

첫 번째 줄에 시작 상태에서의 정답을 출력한다.

다음 $Q$개의 줄 중 $j$번째 줄에 $j$번째 수정 요청을 처리한 후의 정답을 출력한다.

$1 \leq N, Q \leq 2 \times 10^5$

$1 \leq q_j \leq N$

$1 \leq c_i, s_i, c'_j, s'_j \leq 10^9$

수정 요청 전후의 상태가 같을 수도 있다. 즉, $c'_j = c_{q_j}$이고 $s'_j = s_{q_j}$일 수도 있다.