Limak is a brown bear, experienced in organizing programming contests. Today, his only responsibility is to watch the leaderboard and make sure that everything is displayed correctly.

There are n participants, numbered 1 through n. Initially, every participant has 0 points. During the contest participants will gain more points and thus the leaderboard may change.

You are given q queries (events). The i-th query contains two integers \(a_i\) and \(b_i\). It denotes that a participant \(a_i\) gets \(b_i\) points (his/her number of points is increased by \(b_i\)).

For each participant, his or her place is equal to the number of participants with more points, increased by 1. You may refer to the sample explanation for an example.

Let's define hash of participant as the product of his/her place and the number of points. After each query, Limak is going to find the sum of hashes of participants. Can you help him? After each query, print one line with the sum of hashes of participants.

Input format

The first line of the input contains two integers n and q — the number of participants and the number of queries, respectively.

The next q lines describe queries. The i-th of them contains two integers \(a_i\) and \(b_i\) — the participant index and the number of gained points in the i-th query.

Output format

After each query, output a single line containing the sum of hashes of participants.

Constraints

\(1 \le n, q \le 500\,000\)
\(1 \le a_i \le n\)
\(1 \le b_i \le 10^6\)

Subtasks

Extra constraints	Points	Which tests
\(n, q \le 2000\)	25	1-10
\(b_i \le 5\)	25	11-20
each participant will have at most \(10^6\) points	25	21-30
no extra constraints	25	31-40