Truy vấn cập nhật ngẫu nhiên (Random Update Query)

Nguồn: AtCoder

Phiên bản: Phước Hưng OJ Extended

Đề bài

Mỗi thao tác chọn ngẫu nhiên đều một vị trí $p$ trong $[L,R]$ rồi gán $A_p=X$. Sau toàn bộ thao tác, in kỳ vọng của từng $A_i$ theo modulo $998244353$.

Input

Dòng đầu chứa $N,M$. Dòng thứ hai chứa $A_1,A_2,\ldots,A_N$. Mỗi trong $M$ dòng sau chứa L R X, nghĩa là chọn ngẫu nhiên đều một vị trí $p\in[L,R]$ rồi gán $A_p=X$.

Output

In $N$ kỳ vọng cuối cùng theo modulo $998244353$ trên một dòng.

Subtask

• Subtask 1 (20%): $n$ và số thao tác không vượt 30; các điều kiện còn lại giữ như đề đầy đủ.

• Subtask 2 (30%): $n$ và số thao tác không vượt 3000; các điều kiện còn lại giữ như đề đầy đủ.

• Subtask 3 (50%): toàn bộ giới hạn:

• $1\le N,M\le2\cdot10^5$

• $0\le A_i,X_i\le10^9$

Ví dụ

Input

3 2
1 2 3
1 3 6
2 2 10

Output

665496238 10 4

Giải thích

Mỗi thao tác được đổi thành cập nhật affine của kỳ vọng. Sau hai thao tác, ba kỳ vọng theo modulo lần lượt là 665496238 10 4.