Operation Range Maximum Finalization

You are given an integer n representing the length of a sequence a (indexed from 1 to n), initially all zeros. You are also given an integer m and m operations. The i-th operation is described by three integers l_i, r_i and x_i and means that for every index j with li ≤ j ≤ ri, you update

Let \(\mathrm{sol}(l,r)\) denote the sequence obtained after applying operations from l to r (in the given order) starting from the initial sequence. Let \(\mathrm{sol}(1,m)\) be the final sequence after all operations. We say a contiguous block of operations \([l,r]\) is valid if \(\mathrm{sol}(l,r)=\mathrm{sol}(1,m)\).

For each i (\(1\le i\le m\)), let \(f_i\) be the number of indices \(k\) (with \(i \le k \le m\)) such that \(\mathrm{sol}(i,k)=\mathrm{sol}(1,m)\). In other words, \(f_i\) is the number of valid operation segments that start at i.

Your task is to compute the following three numbers modulo \(2^{32}\) (i.e. modulo 4294967296):

1. The total number of valid pairs \((l,r)\) (this is \(\sum_{i=1}^{m} f_i\)).
2. The value of \(\bigoplus_{i=1}^{m} (f_i \times i)\), where \(\oplus\) denotes the bitwise XOR.
3. The value of \(\sum_{i=1}^{m} (f_i \times i)\).

Observation and Hint:

If you simulate all operations from 1 to m, you will get the final sequence \(\mathrm{sol}(1,m)\). Notice that an operation can be considered critical if it is the last operation that sets the maximum value at some position. More precisely, for every index \(j\) such that the final value \(a_j>0\), define \(c(j)\) as the greatest index \(i\) (i.e. the last operation) among those operations covering j for which \(x_i = a_j\). Then if we let \(C = \{ c(j) : 1 \le j \le n \text{ and } a_j>0 \}\), it turns out that a contiguous set of operations \([l,r]\) will yield \(\mathrm{sol}(1,m)\) if and only if it contains every operation index in \(C\). Let c_min and c_max be the minimum and maximum elements of \(C\), respectively. Thus, if \(C\) is nonempty, a segment \([l,r]\) is valid if and only if

• \(l \le c_{min}\) and
• \(r \ge c_{max}\).

If there is no index \(j\) with \(a_j>0\) (i.e. the final sequence remains all zero), then every segment \([l,r]\) is valid.

This observation lets you count the total number of valid segments and compute \(f_i\) for each i easily.

inputFormat

The first line contains two integers n and m (1 ≤ n, m ≤ some moderate limit).

Then, m lines follow. The i-th line contains three integers li ri xi representing the i-th operation.

outputFormat

Output three integers separated by spaces. They are:

• The total number of valid segments \((l,r)\) such that \(\mathrm{sol}(l,r)=\mathrm{sol}(1,m)\).
• The value of \(\bigoplus_{i=1}^{m} (f_i \times i)\).
• The value of \(\sum_{i=1}^{m} (f_i \times i)\).

All answers should be given modulo \(2^{32}\) (i.e. modulo 4294967296).

sample

1 3
1 1 5
1 1 3
1 1 5

3 0 6