# Painting

Time Limit : 3 sec, Memory Limit : 524288 KB

# Problem G: Painting

## Problem

$N$̐$X$^BԂł$X$̗vf͑S$0$łBāA$M$̐̃yA$(A_i, B_i)$^BeyAɑ΂ȉ̑sAŏIIȐ$X$o͂B

• $j$ $(1 \le j \le N)$ɑ΂A$(A_i+j)$$B_i$Ŋ]$X_j$ɉB
• ## Input

͈͂ȉ̌ŗ^B

$N$ $M$
$A_1$ $B_1$
$A_2$ $B_2$
:
$A_M$ $B_M$


$1$sڂɁA^鐔̗vf$N$AyA̐$M$󔒋؂ŗ^B
$M$sɁA$i$Ԗڂ̃yA$(A_i, B_i)$󔒋؂ŗ^B

## Constraints

͈͂ȉ̏𖞂B

• $1 \le N, M \le 10^5$
• $0 \le A_i < B_i \le 10^9 (1 \le i \le M)$
• ^͂͑SĐł

## Output

̐$N$sŏo͂B$j$sڂ$X_j$o͂B

## Sample Input 1

5 3
1 4
3 7
0 1000


## Sample Output 1

7
10
9
5
8


## Sample Input 2

14 12
1 4
2 3
0 5
1 4
1 2
0 8
0 2
0 10
0 1
0 8
3 10
1 10


## Sample Output 2

15
24
25
31
35
44
32
25
24
15
16
25
31
40
`