Showering in the wind

Program time limit: 1 second

Program memory limit: 512 MB

Cyril relies on a unique, entirely natural showering system. For the past 10 years, a constant wind blowing horizontally to the right has swept all the rainwater off his perfectly flat roof, creating a magnificent waterfall for him to shower under at the rightmost edge.

However, disaster has struck. Frank, the strongest man in the universe, recently clashed with Morthak the Destroyer on Cyril’s roof. Their battle left the roof with pits. Now, when the wind pushes the rainwater to the right, the water gets trapped in these pits instead of flowing cleanly off the edge!

The roof can be represented as a 1D coordinate line. There are pits located at various positions $p_i$, each with a specific water capacity $d_i$.

Every afternoon, rain falls on the roof. Specifically, a water source drops $u_i$ units of water at position $x_i$. The wind then immediately blows all the fallen water to the right. As the water flows rightward, any pit it encounters will trap the water until the pit reaches its maximum capacity $d_i$. Any excess water overflows and continues flowing to the right. Whatever water makes it past all the pits and flows off the right edge of the roof is the water Cyril gets to enjoy.

Every morning, the scorching sun evaporates all the water on the roof (emptying all pits completely). However, the rain pattern changes over a period of Q days.

You will process $Q$ days of updates. On each day, first apply that day's update to the set of rain sources, then consider that day's rainfall on an empty roof. Each day features one of two updates:

1 u x: A new rain source appears, dropping $u$ units of water at position $x$.

2 x: All rain currently falling at position $x$ is removed.

If multiple rain sources exist at the same position, treat them as a single combined source whose amount is the sum of their amounts.

Output: At the end of each of the Q days, output a single integer: the total units of rainwater that successfully flow off the right edge of the roof for Cyril to enjoy.

Input

The first line of input contains two integers, $N$ and $M$, where $N$ is the initial number of rain sources and $M$ is the number of pits.
Then follow $M$ lines. The $i$th contains two integers $d_i$ and $p_i$, the capacity and position of the $i$th pit.
Then follow $N$ lines. The $i$th contains two integers $u_i$ and $x_i$, the amount of water and the position of the $i$th rain source.
The next line contains one integer $Q$.
Then follow $Q$ lines, each of which is either:
1. 1 u x, adding $u$ units of rain at position $x$.
2. 2 x, removing all rain at position $x$.

You should read from standard input.

Constraints

For all test cases:

$0 \le N, M, Q \le 10^5$.
$1 \le u_i,x_i,d_i,p_i \le 10^9$.
It is possible to have multiple rain sources at the same position, but pit positions are distinct.

Additionally:

For Subtask 1 (30% of points): $0 \le N, M, Q \le 10^3$.
For Subtask 2 (70% of points): there are no additional constraints.

Output

At the end of each day, you should output the amount of water that falls on Cyril's head. You should write to standard output.

Sample Input 1

Sample Output 1

4
1

Explanation 1

Day 1, four units of water will pass through to Cyril's head.
Day 2, one unit of water will pass through to Cyril's head.

Scoring

For each subtask (worth 30% and 70% of points, as per the Constraints section), your program will be run on multiple secret test cases one after another, and if it produces the correct output for all test cases, it solves that subtask. Your program will receive the points for each subtask it solves. Recall that your final score on the task is the score of your highest scoring submission.

Submit unofficially

The contest ended at 8:45 p.m. AEST on Tuesday 7th April. All submissions will be unofficial officially.