쿠키 공장

유민이의 쿠키 공장에 $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}$일 수도 있다.