Track Solved Problems

In this problem, you are given a programming contest with ( Q ) problems and ( M ) submissions made by a contestant. Each submission is represented as a pair of integers ( (p, r) ) where ( p ) is the problem number (from 1 to ( Q )) and ( r ) is the result of the submission: 1 indicates a correct submission and 0 indicates an incorrect one. A problem is considered solved only when it is submitted correctly for the first time. Subsequent submissions for a problem which has already been solved (regardless of correctness) do not affect the total count of solved problems. Your task is to process the submissions in the order they are received and determine the cumulative number of problems solved after each submission.

For example, if ( Q = 4 ) and the submissions are:

1 1 2 0 2 1 3 1

then the cumulative counts after each submission would be: 1, 1, 2, 3.

inputFormat

The first line of the input contains two integers ( Q ) and ( M ) separated by a space, where ( Q ) is the number of problems and ( M ) is the number of submissions. The following ( M ) lines each contain two integers ( p ) and ( r ), representing a submission. ( p ) indicates the problem number (1-indexed) and ( r ) is either 0 (incorrect) or 1 (correct).

outputFormat

Output ( M ) integers separated by spaces on a single line. The ( i^{th} ) integer should represent the total number of distinct problems solved up to and including the ( i^{th} ) submission.## sample

4 4
1 1
2 1
3 1
4 1

1 2 3 4