压痕

时间限制：$2.0\text{ s}$

空间限制：$256\text{ MiB}$

题目描述

印刷厂在折叠一批连续纸带前，需要先用压线辊反复加深若干段预定折痕。为了检查纸带是否会因压力过度集中而破损，把纸带离散为从 $1$ 到 $n$ 的 $n$ 个测量位置。开始时，每个位置记录的累计压痕深度均为 $0$。

压线辊每次会作用于一段闭区间 $[l,r]$。辊面中部的压力最大，向两端按整数梯度逐级减小，两端位置的增量均为 $1$。具体地，这次操作使每个 $l\le i\le r$ 的压痕深度增加

区间长度为偶数时，中间的两个位置获得相同的最大增量。不同次压线的影响直接累加，纸带在全部操作结束前不会回弹。

一共进行 $q$ 次压线。请给出最终的最大压痕深度、达到该深度的位置个数，以及全部 $n$ 个位置的压痕深度总和。

输入格式

第一行两个正整数 $n,q$，分别表示纸带长度和操作次数。

接下来 $q$ 行，每行两个整数 $l,r$，表示一次操作覆盖的区间。

输出格式

输出一行三个整数，依次表示最大压痕深度、达到最大深度的位置个数、所有位置的压痕深度之和。

输入样例 1

5 1
1 5

输出样例 1

3 1 9

输入样例 2

6 3
1 4
3 6
2 5

输出样例 2

5 2 18

输入样例 3

见附件 sample/crease3.in

输出样例 3

见附件 sample/crease3.out

数据范围

对于所有测试点，保证 $1\le n,q\le 5\times 10^5$，$1\le l\le r\le n$。

每个测试点单独计分。