Analyzing Contracts

Doctor Kruskal is starting a tiberium trading business. There are N possible suppliers of tiberium, and many clients want to receive tiberium to run their industries. Calendar days are numbered with positive integers, and each supplier is identified by a distinct integer from 1 to N. Supplier i can supply tiberium from day $S_i$ onwards, but not on earlier days. The supplier charges $P_i$ dollars per day. The list contains only the best suppliers in the city, so $S_i < S_{i+1}$ and $P_i > P_{i+1}$ for $i = 1, \dots, N-1$.

The first line contains N ($1 \le N \le 2 \times 10^5$). Each of the next N lines contains $S_i$ and $P_i$ ($1 \le S_i, P_i \le 10^9$). The next line contains Q ($1 \le Q \le 2 \times 10^5$). Each of the next Q lines is either c E R ($1 \le E, R \le 10^9$), which adds a client with end day E and daily revenue R to the database, or s I ($1 \le I \le N$), which asks for the maximum profit for supplier I. At least one operation of the second type appears.

For each operation of type s, print one line with the maximum possible profit from matching an available client with the given supplier. Print the results in the order the operations appear in the input.