该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

文件输入输出提示

本题采用文件输入输出。提交代码时，请在 main 函数开头加入文件重定向，并从 signal.in 读入、输出到 signal.out。

freopen("signal.in", "r", stdin);
freopen("signal.out", "w", stdout);

题目描述

苗苗负责在学校的一条走廊中布置信号器。走廊上有 $M$ 个位置，编号为 $1$ 到 $M$。

第 $i$ 个信号器可以覆盖编号从 $l_i$ 到 $r_i$ 的所有位置，包括 $l_i$ 和 $r_i$。

请你统计：

1. 有多少个位置没有被任何信号器覆盖；
2. 有多少个位置恰好被一个信号器覆盖；
3. 一个位置最多会被多少个信号器同时覆盖。

输入格式

从文件 signal.in 中读入数据。

第一行输入两个整数 $M,N$，表示走廊长度和信号器数量。

接下来 $N$ 行，每行输入两个整数 $l_i,r_i$，表示一个信号器的覆盖区间。

输出格式

输出到文件 signal.out 中。

输出一行三个整数，分别表示没有被覆盖的位置数量、恰好被一个信号器覆盖的位置数量、最大覆盖次数。

输入输出样例 #1

输入 #1

10 4
1 3
3 5
7 10
8 8

输出 #1

1 7 2

说明/提示

第 6 个位置没有被任何信号器覆盖。

位置 $1,2,4,5,7,9,10$ 恰好被一个信号器覆盖，共 7 个。

位置 $3$ 和 $8$ 都被两个信号器覆盖，因此最大覆盖次数为 2。

输入输出样例 #2

输入 #2

6 0

输出 #2

6 0 0

第二个样例中，没有布置任何信号器，所以 6 个位置都没有被覆盖，最大覆盖次数为 0。

数据范围与子任务

对于所有数据，满足：

• $1\le M\le 10^6$；
• $0\le N\le 2\times 10^5$；
• $1\le l_i\le r_i\le M$。

signal_大样例.zip