Random Update Query

Source: AtCoder

Version: Phuoc Hung OJ Extended

Problem Statement

Each operation chooses a uniformly random position in a range and sets it to $X$. Output every final expected value modulo $998244353$.

Input

The first line contains $N,M$. The second line contains $A_1,\ldots,A_N$. Each of the next $M$ lines contains L R X: choose one position uniformly from $[L,R]$ and set its value to $X$.

Output

Print the $N$ final expected values modulo $998244353$ on one line.

Subtasks

• Subtask 1 (20%): size and operation count at most 30; all other validity conditions are unchanged.

• Subtask 2 (30%): size and operation count at most 3000; all other validity conditions are unchanged.

• Subtask 3 (50%): full constraints:

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

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

Examples

Input

3 2
1 2 3
1 3 6
2 2 10

Output

665496238 10 4

Explanation

Each operation becomes an affine update of expectations. After both operations, the expected values modulo 998244353 are 665496238 10 4.