[Solved] Train Maintenance solution codeforces – There are nn models of trains, and Nitori’s department will only have at most one train of each model at any moment. In the beginning, there are no trains, at each of the following mm days, one train will be added, or one train will be removed.

Train Maintenance solution codeforces

Kawasiro Nitori is excellent in engineering. Thus she has been appointed to help maintain trains.

There are nn models of trains, and Nitori’s department will only have at most one train of each model at any moment. In the beginning, there are no trains, at each of the following mm days, one train will be added, or one train will be removed. When a train of model ii is added at day tt, it works for xixi days (day tt inclusive), then it is in maintenance for yiyi days, then in work for xixi days again, and so on until it is removed.

In order to make management easier, Nitori wants you to help her calculate how many trains are in maintenance in each day.

Train Maintenance solution codeforces

Input

The first line contains two integers nnmm (1n,m21051≤n,m≤2⋅105).

The ii-th of the next nn lines contains two integers xi,yixi,yi (1xi,yi1091≤xi,yi≤109).

Each of the next mm lines contains two integers opopkk (1kn1≤k≤nop=1op=1 or op=2op=2). If op=1op=1, it means this day’s a train of model kk is added, otherwise the train of model kk is removed. It is guaranteed that when a train of model xx is added, there is no train of the same model in the department, and when a train of model xx is removed, there is such a train in the department.

Output

Print mm lines, The ii-th of these lines contains one integers, denoting the number of trains in maintenance in the ii-th day.

Train Maintenance solution codeforces

Examples
input

Copy
3 4
10 15
12 10
1 1
1 3
1 1
2 1
2 3

output

Copy
0
1
0
0

input

Copy
5 4
1 1
10000000 100000000
998244353 1
2 1
1 2
1 5
2 5
1 5
1 1

output

Copy
0
0
0
1

Train Maintenance solution codeforces
Note

Consider the first example:

The first day: Nitori adds a train of model 33. Only a train of model 33 is running and no train is in maintenance.

The second day: Nitori adds a train of model 11. A train of model 11 is running and a train of model 33 is in maintenance.

The third day: Nitori removes a train of model 11. The situation is the same as the first day.

The fourth day: Nitori removes a train of model 33. There are no trains at all.

Also read : Counting Tuples codechef solution