### PROBLEM LINK:

**Author:** Dmytro Berezin

**Tester:** Sergey Kulik

**Editorialist:** Lalit Kundu

### DIFFICULTY:

EASY

### PREREQUISITES:

AD-HOC

### PROBLEM:

There is a N * M matrix, where A[i][j] is j for all i,j. There are P queries of form (i,j), where we do A[i][j]++.

For each row i,

if there exists a j, such that A[i][j] > A[i][j+1], print -1.

else print sum[i=M to 2]{A[i][j]-A[i][j-1]}.

1 ≤ N,M,P ≤ 10^{5}

### QUICK EXPLANATION:

For each i, we also keep note of values (i,j-1) and (i,j+1), if (i,j) is given in input. Traversing over the queries, we can see which values change and print answer accordingly.

### EXPLANATION:

We have to process for each i independently. Let’s say for an i, we have NN queries of form (j,k) which means: increase A[i][j] by k. For such a query we also store (j-1,0) and (j+1,0), because these two indexes are also effected.

If there were no changes, our answer will be m-1. Now, we traverse over all queries in increasing order of j and look at index j+1, if the value at j+1 is less than value at j, we know that answer is -1 for this row. Else, we add the (A[i][j+1]-A[i][j]) to the answer and subtract -1 from the answer. We can use map to perform this process efficiently. See (setter/tester/editorialist)'s solution for implementation details.