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

见题面

见题面