Cho mảng ~a~ gồm ~n~ phần tử. Ban đầu, các phần tử đều có giá trị là ~0~.

Có ~q~ truy vấn, mỗi truy vấn gồm ba số nguyên dương ~l~, ~r~, ~x~ với ý nghĩa: xét đoạn con liên tiếp từ ~l~ đến ~r~ trên mảng ~a~, tăng ~a_i~ lên một lượng ~x \times (i - l + 1)~ với ~l \le i \le r~.

Hãy in ra tổng của các phần tử trong mảng ~a~ sau ~q~ truy vấn.

INPUT

Dòng đầu tiên chứa số nguyên dương ~n~ và ~q~ (~1 \le n \le 2 \times 10^8~, ~1 \le q \le 10^6~).

~q~ dòng tiếp theo, mỗi dòng chứa ba số nguyên dương ~l~, ~r~ và ~x~ (~1 \le l \le r \le n~, ~1 \le x \le 10^9~).

OUTPUT

Dòng duy nhất là tổng các phần tử trong mảng ~a~ sau khi thực hiện ~q~ truy vấn.

Vì kết quả có thể rất lớn, hãy in ra phần dư của kết quả khi chia cho ~20032024~.

SAMPLE INPUT

5 3
1 2 1
2 3 1
3 5 2

SAMPLE OUTPUT

18

Mảng sau khi thực hiện tất cả các truy vấn là ~[1, 3, 4, 4, 6]~.

SUBTASKS