题目背景

轻快的音乐声坚定了你做一道简单题的决心。

（题目背景图片来自 Phigros 曲绘，如有侵权，请告知出题人。）

题目描述

你有一个长度为 $n$，初值全为 $0$ 的序列 $a$。

你有长为 $m$ 的操作序列，其中第 $i$ 次有三个参数 $l_i,r_i,x_i$，表示令 $\forall j\in[l_i,r_i] ,a_j\gets\max(a_j,x_i)$。

令 $\text{sol}(l,r)$ 表示依次操作第 $l$ 至第 $r$ 个操作后的 $a$ 序列。

你需要回答有多少对 $(l,r)$ 满足 $1\le l\le r\le m$ 且 $\text{sol}(l,r)=\text{sol}(1,m)$。

记 $f_i$ 为有多少 $i\le k\le m$ 满足 $\text{sol}(i,k)=\text{sol}(1,m)$，你还需要输出 $\displaystyle\bigoplus_{i=1}^m f_i\times i$ 与 $\displaystyle\sum_{i=1}^m f_i\times i$ 的值。

所有答案都需要对 $2^{32}$ 取模后输出。

输入格式

第一行两个整数 $n,m$。
接下来 $m$ 行，每行三个整数 $l_i,r_i,x_i$，表示第 $i$ 个操作。

输出格式

一行三个整数表示答案。

5 5
1 3 1
2 4 1
2 3 1
1 3 1
1 4 1

9 2 20

3 5
1 3 2
1 1 1
2 2 2
3 3 3
1 3 2

5 7 11

提示

Idea：cyffff，Solution：Ntokisq / abruce，Code：cyffff，Data：cyffff

月下缭乱 - 月見静華 vs. LUNARiUM (Insane14.8)

本题输入输出文件较大，请使用恰当的输入输出方式。

样例解释

对于样例 $1$，最终 $a$ 序列的值为 $\{1,1,1,1,0\}$。不难发现，进行 $[1,2],[1,3],[1,4],[2,4],[1,5],[2,5],$$[3,5],[4,5],[5,5]$ 内的操作都可以使得 $a$ 与进行所有操作后 $a$ 序列的值相同。答案为 $9$。$f$ 序列为 $\{4,2,1,1,1\}$。

对于样例 $2$，最终 $a$ 序列的值为 $\{2,2,3\}$。不难发现，进行 $[1,4],[1,5],[2,5],[3,5],[4,5]$ 内的操作都可以使得 $a$ 与进行所有操作后 $a$ 序列的值相同。答案为 $5$。$f$ 序列的值为 $\{2,1,1,1,0\}$。

数据规模

本题采用捆绑测试。

$\text{Subtask}$	$n,m\le$	特殊限制	$\text{Score}$
$1$	$100$	无	$10$
$2$	$10^4$		$20$
$3$	$3\times10^5$	保证 $l_i=r_i$	$10$
$4$		保证 $x_i=1$
$5$		无	$20$
$6$	$10^6$		$30$

对于 $100\%$ 的数据，$1\le n,m\le10^6$，$1\le l_i\le r_i\le n$，$1\le x_i\le m$。

特殊评分方式

本题开启子任务依赖，具体如下：

• 对于子任务 $i\in\{1,3,4\}$，您只需答对子任务 $i$ 即可获得子任务 $i$ 的分数。
• 对于子任务 $i\in\{2,5,6\}$，您需要答对所有 $j\in[1,i]$ 的子任务 $j$ 才能获得子任务 $i$ 的分数。