{"raw_statement":[{"iden":"background","content":"![](https://cdn.luogu.com.cn/upload/image_hosting/xkd5zhgk.png?x-oss-process=image)\n\n轻快的音乐声坚定了你做一道简单题的决心。\n\n（题目背景图片来自 Phigros 曲绘，如有侵权，请告知出题人。）"},{"iden":"statement","content":"你有一个长度为 $n$，初值全为 $0$ 的序列 $a$。\n\n你有长为 $m$ 的操作序列，其中第 $i$ 次有三个参数 $l_i,r_i,x_i$，表示令 $\\forall j\\in[l_i,r_i] ,a_j\\gets\\max(a_j,x_i)$。\n\n令 $\\text{sol}(l,r)$ 表示依次操作第 $l$ 至第 $r$ 个操作后的 $a$ 序列。\n\n你需要回答有多少对 $(l,r)$ 满足 $1\\le l\\le r\\le m$ 且 $\\text{sol}(l,r)=\\text{sol}(1,m)$。\n\n记 $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$ 的值。\n\n所有答案都需要对 $2^{32}$ 取模后输出。"},{"iden":"input","content":"第一行两个整数 $n,m$。\n\n接下来 $m$ 行，每行三个整数 $l_i,r_i,x_i$，表示第 $i$ 个操作。"},{"iden":"output","content":"一行三个整数表示答案，对 $2^{32}$ 取模。"},{"iden":"note","content":"Idea：cyffff，Solution：Ntokisq / abruce，Code：cyffff，Data：cyffff\n\n**月下缭乱 - 月見静華 vs. LUNARiUM (Insane14.8)**\n\n**本题输入输出文件较大，请使用恰当的输入输出方式。**\n\n### 样例解释\n\n对于样例 $2$，最终 $a$ 序列的值为 $\\{2,2,3\\}$。不难发现，进行 $[1,4],[1,5],[2,5],[3,5],[4,5]$ 内的操作都可以使得 $a$ 与进行所有操作后 $a$ 序列的值相同。答案为 $5$。$f$ 序列的值为 $\\{2,1,1,1,0\\}$。\n\n### 数据规模\n本题采用捆绑测试。\n\n::cute-table\n| $\\text{Subtask}$ | $n,m\\le$ | 特殊限制 | $\\text{Score}$ |\n| :----------: | :----------: | :----------: | :----------: |\n| $1$ | $100$ | 无 | $10$ |\n| $2$ | $10^4$ | ^ | $20$ |\n| $3$ | $3\\times10^5$ | 保证 $l_i=r_i$ | $10$ |\n| $4$ | ^ | 保证 $x_i=1$ | $10$ |\n| $5$ | ^ | 无 | $20$ |\n| $6$ | $10^6$ | ^ | $30$ |\n\n对于 $100\\%$ 的数据，$1\\le n,m\\le10^6$，$1\\le l_i\\le r_i\\le n$，$1\\le x_i\\le m$。\n### 特殊评分方式\n本题开启子任务依赖，具体如下：\n- 对于子任务 $i\\in\\{1,3,4\\}$，您只需答对子任务 $i$ 即可获得子任务 $i$ 的分数。\n- 对于子任务 $i\\in\\{2,5,6\\}$，您需要答对所有 $j\\in[1,i]$ 的子任务 $j$ 才能获得子任务 $i$ 的分数。"}],"translated_statement":null,"sample_group":[["5 5\n1 3 1\n2 4 1\n2 3 1\n1 3 1\n1 4 1\n","9 2 20"],["3 5\n1 3 2\n1 1 1\n2 2 2\n3 3 3\n1 3 2\n","5 7 11"]],"show_order":[],"formal_statement":null,"simple_statement":null,"has_page_source":false}