Description

幼儿园N个同学排成一列准备去幼儿园，老师将其编号为1～N。出发前老师给每人带了一顶小白帽，然后老师开展了M次戴帽操作，其中第i次操作是给编号区间为[x,y]小朋友戴上小红帽。

请你帮忙输出每次戴帽操作后队伍中小白帽剩余的人数。

Format

Input

输入一行为N和M。下面M行每行两个数x、y

N,M<=2e5

Output

输出M行，为每次操作后剩余小白帽人数

Samples

10 3 
3 3 
5 7 
2 8

9 
6 
3