Problem A: A White Wall

Background

とある都市に住むＡ氏の家の敷地は、真っ白な壁に囲まれている。壁に物足りなさを感じたＡ氏は、近所の子供たちを呼んで、壁を自由に塗ってもらうことにした。子供達にはそれぞれ壁の好きな区間を選んで色を塗ってもらう。 さて、壁はどのように塗られただろうか。

Problem

0〜N-1の区画で構成される以下のような円型の白い壁がある。

M人の子供たちがこの壁の開始位置aと開始位置からの長さLを指定し、反時計回りにaから(a+L) mod Nまで色を塗る(ただし、a mod Nとは、aをNで割ったときの余りを表す)。ここで、他の人が色を塗った区間と重ねて塗ることもでき、その場合は、色が塗られた1つの区間とみなす。色が塗られた区間を大きい順に出力せよ。また、その大きさの区間がいくつあるかも同時に出力せよ。

Input

入力は以下の形式で与えられる。

N M
a0 L0 
a1 L1 
...
aM−1 LM−1 

1行目にそれぞれ壁の長さと壁に色を塗る人の数を表す2つの整数N,Mが空白区切りで与えられる。続くM行には、各人が色を塗る区間の開始位置a_iと長さL_iが与えられる。

Constrains

入力は以下の条件を満たす

• 2 ≤ N ≤ 100
• 1 ≤ M ≤ 50
• 0 ≤ a_i < N
• 1 ≤ L_i ≤ N

Output

色が塗られた区間の長さとその長さの総数を色が塗られた区間が大きい順に出力する。

Sample Input 1

5 3
0 1
2 1
3 1

Sample Output 1

2 1
1 1

Sample Input 2

4 2
0 2
1 2

Sample Output 2

3 1

Sample Input 3

10 3
2 1
4 1
9 2

Sample Output 3

2 1
1 2