Có ~N~ cây được đánh số từ ~1~ đến ~N~. Ban đầu, vào ngày ~0~, tất cả các cây đều không có quả.

Từ ngày ~1~ trở đi, vào mỗi buổi sáng, cây thứ ~i~ mọc thêm đúng ~i~ quả.

Có ~Q~ lần thu hoạch. Lần thu hoạch thứ ~i~ được thực hiện vào buổi tối ngày ~D_i~. Khi đó, toàn bộ số quả đang có trên các cây từ ~L_i~ đến ~R_i~ đều được thu hoạch. Sau lần thu hoạch, các cây trong đoạn này trở về ~0~ quả.

Với mỗi lần thu hoạch, hãy tính số quả thu được modulo ~998244353~.

Ràng buộc

• ~1 \le N \le 10^{18}~
• ~1 \le Q \le 2 \times 10^5~
• ~1 \le D_1 < D_2 < \dots < D_Q \le 10^{18}~
• ~1 \le L_i \le R_i \le N~
• Mọi giá trị trong input đều là số nguyên.

Input

Dòng đầu gồm hai số nguyên ~N, Q~.

~Q~ dòng tiếp theo, dòng thứ ~i~ gồm ba số nguyên:

~D_i\ L_i\ R_i~

mô tả lần thu hoạch thứ ~i~.

Output

In ra ~Q~ dòng.

Dòng thứ ~i~ chứa số quả thu được trong lần thu hoạch thứ ~i~, lấy modulo ~998244353~.

Ví dụ 1

Input

5 3
2 2 3
3 3 4
5 1 5

Output

10
15
50

Ví dụ 2

Input

711741968710511029 1
82803157126515475 516874290286751784 588060532191410838

Output

603657470