Sushi

Input

The input is given from Standard Input in the following format:

$N \ Q$ $a_1 \ b_1$ $a_2 \ b_2$ $： \ ：$ $a_Q \ b_Q$

Output

• You have to print $N$ lines.
• The $i$-th line should contain the number of dishes of sushi had eaten for customer $i (1 \le i \le N)$.

Constraints

• $3 \le N, Q \le 100,000$
• $1 \le a_i \le N$
• $1 \le b_i \le 10^{12}$
• Any final results do not exceed $2 \times 10^{13}$.

Subtasks

Subtask 1 [ $60$ points ]

• $N, Q \le 100$
• $b_i = 1$

Subtask 2 [ $400$ points ]

• $N, Q \le 100$
• $b_i \le 10^{12}$

Subtask 3 [ $240$ points ]

• $N, Q \le 100,000$
• $b_i = 1$

Subtask 4 [ $500$ points ]

• There are no additional constraints.

Output

• You have to print $N$ lines.
• The $i$-th line should contain the number of dishes of sushi had eaten for customer $i (1 \le i \le N)$.

Constraints

• $3 \le N, Q \le 100,000$
• $1 \le a_i \le N$
• $1 \le b_i \le 10^{12}$
• Any final results do not exceed $2 \times 10^{13}$.

Subtasks

Subtask 1 [ $60$ points ]

• $N, Q \le 100$
• $b_i = 1$

Subtask 2 [ $400$ points ]

• $N, Q \le 100$
• $b_i \le 10^{12}$

Subtask 3 [ $240$ points ]

• $N, Q \le 100,000$
• $b_i = 1$

Subtask 4 [ $500$ points ]

• There are no additional constraints.

Input

The input is given from Standard Input in the following format:

$N \ Q$ $a_1 \ b_1$ $a_2 \ b_2$ $： \ ：$ $a_Q \ b_Q$

Examples

Input

9 3 5 11 8 4 4 7

Output

4 4 4 4 2 2 1 1 0

Input

6 6 3 5 6 11 1 6 4 7 5 2 2 5

Output

10 10 5 5 4 2

Input

5 6 1 1 2 1 3 1 1 1 5 1 3 1

Output

2 2 1 1 0

Input

10 10 10 10 9 20 8 30 7 40 6 50 5 60 4 70 3 80 2 90 1 100

Output

223 123 77 50 33 21 12 7 3 1

inputFormat

Input

The input is given from Standard Input in the following format:

$N \ Q$ $a_1 \ b_1$ $a_2 \ b_2$ $： \ ：$ $a_Q \ b_Q$

outputFormat

Output

• You have to print $N$ lines.
• The $i$-th line should contain the number of dishes of sushi had eaten for customer $i (1 \le i \le N)$.

Constraints

• $3 \le N, Q \le 100,000$
• $1 \le a_i \le N$
• $1 \le b_i \le 10^{12}$
• Any final results do not exceed $2 \times 10^{13}$.

Subtasks

Subtask 1 [ $60$ points ]

• $N, Q \le 100$
• $b_i = 1$

Subtask 2 [ $400$ points ]

• $N, Q \le 100$
• $b_i \le 10^{12}$

Subtask 3 [ $240$ points ]

• $N, Q \le 100,000$
• $b_i = 1$

Subtask 4 [ $500$ points ]

• There are no additional constraints.

Output

• You have to print $N$ lines.
• The $i$-th line should contain the number of dishes of sushi had eaten for customer $i (1 \le i \le N)$.

Constraints

• $3 \le N, Q \le 100,000$
• $1 \le a_i \le N$
• $1 \le b_i \le 10^{12}$
• Any final results do not exceed $2 \times 10^{13}$.

Subtasks

Subtask 1 [ $60$ points ]

• $N, Q \le 100$
• $b_i = 1$

Subtask 2 [ $400$ points ]

• $N, Q \le 100$
• $b_i \le 10^{12}$

Subtask 3 [ $240$ points ]

• $N, Q \le 100,000$
• $b_i = 1$

Subtask 4 [ $500$ points ]

• There are no additional constraints.

Input

The input is given from Standard Input in the following format:

$N \ Q$ $a_1 \ b_1$ $a_2 \ b_2$ $： \ ：$ $a_Q \ b_Q$

Examples

Input

9 3 5 11 8 4 4 7

Output

4 4 4 4 2 2 1 1 0

Input

6 6 3 5 6 11 1 6 4 7 5 2 2 5

Output

10 10 5 5 4 2

Input

5 6 1 1 2 1 3 1 1 1 5 1 3 1

Output

2 2 1 1 0

Input

10 10 10 10 9 20 8 30 7 40 6 50 5 60 4 70 3 80 2 90 1 100

Output

223 123 77 50 33 21 12 7 3 1

样例

6 6
3 5
6 11
1 6
4 7
5 2
2 5

10
10
5
5
4
2

</p>