Cho một dãy số $a_1, a_2, \dots, a_N$ có độ dài $N$. Ban đầu, tất cả các phần tử $a_i$ đều bằng $0$. Ta có thể thay đổi dãy số $a$ bằng cách sử dụng các truy vấn sau:

$l \ r \ c$: Thay đổi các giá trị từ vị trí thứ $l$ đến vị trí thứ $r$ trong dãy $a$ thành $c$.

Khi có $Q$ truy vấn, ta định nghĩa $f(U, D, L, R)$ là "giá trị của $a_L + a_{L+1} + \dots + a_R$ sau khi thực hiện lần lượt các truy vấn từ thứ $U$ đến thứ $D$". Nếu thực hiện $f$ nhiều lần, mỗi lần thực hiện là độc lập với nhau, nghĩa là các lần thực hiện $f$ trước đó không ảnh hưởng đến lần thực hiện $f$ hiện tại.

Hãy tính tổng $\sum_{U=1}^{Q} \sum_{D=U}^{Q} \sum_{L=1}^{N} \sum_{R=L}^{N} f(U, D, L, R)$ chia lấy dư cho $998\,244\,353$ ($= 119 \times 2^{23} + 1$). Số $998\,244\,353$ là một số nguyên tố.

Dữ liệu vào

• Dòng đầu tiên chứa hai số nguyên $N$ và $Q$ cách nhau bởi dấu cách ($1 \le N, Q \le 300\,000$).
• Từ dòng thứ hai trở đi, mỗi dòng chứa một truy vấn trong số $Q$ truy vấn theo thứ tự. Truy vấn thứ $i$ gồm ba số nguyên $l_i, r_i, c_i$ cách nhau bởi dấu cách ($1 \le l_i \le r_i \le N; 0 \le c_i < 998\,244\,353$).

Dữ liệu ra

• In ra kết quả của $\sum_{U=1}^{Q} \sum_{D=U}^{Q} \sum_{L=1}^{N} \sum_{R=L}^{N} f(U, D, L, R)$ chia lấy dư cho $998\,244\,353$.

Ví dụ

Ví dụ 1

2 2
1 2 1
2 2 2

Ví dụ 1

14

Ví dụ 2

10 10
10 10 593603443
4 9 993565789
3 8 238321270
7 8 424480868
10 10 556869540
8 10 279674600
7 8 575417117
6 8 948583421
6 6 468656456
4 10 865607491

Ví dụ 2

830609277

Ghi chú

Đối với ví dụ đầu tiên:

$f(1, 1, 1, 1) = 1$ $f(1, 1, 1, 2) = 1 + 1 = 2$ $f(1, 1, 2, 2) = 1$ $f(1, 2, 1, 1) = 1$ $f(1, 2, 1, 2) = 1 + 2 = 3$ $f(1, 2, 2, 2) = 2$ $f(2, 2, 1, 1) = 0$ $f(2, 2, 1, 2) = 0 + 2 = 2$ $f(2, 2, 2, 2) = 2$

Do đó, đáp án là $1 + 2 + 1 + 1 + 3 + 2 + 0 + 2 + 2 = 14$.