Background

The light and lively music strengthens your determination to solve an easy problem.

(The background image comes from a Phigros song illustration. If there is any infringement, please inform the problem setter.)

Problem Description

You have a sequence $a$ of length $n$, with all initial values equal to $0$.

You have an operation sequence of length $m$. The $i$-th operation has three parameters $l_i, r_i, x_i$, meaning that for all $j \in [l_i, r_i]$, set $a_j \gets \max(a_j, x_i)$.

Let $\text{sol}(l,r)$ denote the sequence $a$ after applying operations $l$ through $r$ in order.

You need to answer how many pairs $(l,r)$ satisfy $1 \le l \le r \le m$ and $\text{sol}(l,r) = \text{sol}(1,m)$.

Let $f_i$ be the number of $k$ with $i \le k \le m$ such that $\text{sol}(i,k) = \text{sol}(1,m)$. You also need to output the values of $\displaystyle\bigoplus_{i=1}^m f_i \times i$ and $\displaystyle\sum_{i=1}^m f_i \times i$.

All answers should be output modulo $2^{32}$.

Input Format

The first line contains two integers $n, m$.

The next $m$ lines each contain three integers $l_i, r_i, x_i$, describing the $i$-th operation.

Output Format

Output three integers in one line, representing the answers modulo $2^{32}$.

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

Hint

Idea: cyffff, Solution: Ntokisq / abruce, Code: cyffff, Data: cyffff.

Moonlit Dazzle - Tsukimi Shizuka vs. LUNARiUM (Insane14.8)

The input and output files for this problem are large, so please use appropriate I/O methods.

Sample Explanation

For sample $2$, the final sequence $a$ is $\{2,2,3\}$. It is easy to see that applying the operations in $[1,4]$, $[1,5]$, $[2,5]$, $[3,5]$, and $[4,5]$ can all make $a$ the same as the sequence after applying all operations. The answer is $5$. The sequence $f$ is $\{2,1,1,1,0\}$.

Constraints

This problem uses bundled testdata.

::cute-table | $\text{Subtask}$ | $n,m\le$ | Special Constraints | $\text{Score}$ | | :----------: | :----------: | :----------: | :----------: | | $1$ | $100$ | None | $10$ | | $2$ | $10^4$ | ^ | $20$ | | $3$ | $3\times10^5$ | Guaranteed $l_i=r_i$ | $10$ | | $4$ | ^ | Guaranteed $x_i=1$ | $10$ | | $5$ | ^ | None | $20$ | | $6$ | $10^6$ | ^ | $30$ |

For $100\%$ of the testdata, $1 \le n,m \le 10^6$, $1 \le l_i \le r_i \le n$, $1 \le x_i \le m$.

Special Scoring

This problem enables subtask dependencies, as follows.

• For subtask $i \in \{1,3,4\}$, you only need to solve subtask $i$ correctly to get the score of subtask $i$.
• For subtask $i \in \{2,5,6\}$, you need to solve all subtasks $j \in [1,i]$ correctly to get the score of subtask $i$.

Translated by ChatGPT 5