계약 분석

Kruskal 박사는 타이베리움 거래 사업을 시작하려고 한다. 타이베리움 공급업체는 N곳이 있고, 자기 산업에 쓰려고 타이베리움을 받고 싶어 하는 고객도 많다. 날짜는 양의 정수로 번호를 매기며, 각 공급업체는 1부터 N까지 서로 다른 정수로 구분한다. 공급업체 i는 $S_i$일부터 타이베리움을 공급할 수 있고, 그 이전 날에는 공급할 수 없다. 공급 비용은 하루에 $P_i$ 달러이다. 목록에는 도시에서 가장 좋은 공급업체만 있으므로, $i = 1, \dots, N-1$에 대해 $S_i < S_{i+1}$이고 $P_i > P_{i+1}$이다.

첫 줄에 정수 N ($1 \le N \le 2 \times 10^5$)이 주어진다. 이어지는 N개의 줄에는 각각 $S_i$와 $P_i$ ($1 \le S_i, P_i \le 10^9$)가 주어진다. 다음 줄에는 정수 Q ($1 \le Q \le 2 \times 10^5$)가 주어진다. 이어지는 Q개의 줄은 고객을 추가하는 c E R ($1 \le E, R \le 10^9$) 또는 공급업체 I의 최대 이익을 묻는 s I ($1 \le I \le N$) 중 하나이다. 두 번째 종류의 연산이 최소 한 번 나온다.

s 연산마다 한 줄을 출력한다. 그 줄에는 데이터베이스의 고객 중 한 명을 해당 공급업체와 매칭했을 때 얻을 수 있는 최대 이익을 적는다. 결과는 입력에 나온 순서대로 출력한다.