Description

现有 $m$ 个四元组 $(q_k,l_k,r_k,v_k)$，整数序列 $a$ 满足：

$$a_i=\left ( \sum_{k=1}^{m} \ [l_k \le i \le r_k]\ v_k\ (i-l_k+1)^{q_k} \right) \bmod 998244353 $$

请你计算出序列 $a$。

Format

Input

第一行两个正整数 $n,m$，表示 $a$ 的长度与四元组的个数。

接下来 $m$ 行，每行四个正整数 $q_k,l_k,r_k,v_k$。$(0 \le q_k \le 10,\ 1 \le l_k \le r_k \le n,\ 1 \le v_k \le 10^8)$

Output

输出一行 $n$ 个数，表示 $a_{1\ \dots \ n}$ 的值。

Samples

5 3
1 1 2 4
2 3 5 2
0 1 5 5

9 13 7 13 23

5 3
10 1 5 1
9 1 5 2
8 1 5 3

6 2816 118098 1769472 14843750

Limitation

对于 $20\%$ 的数据，保证 $1 \le n,m \le 1000$。

对于另外 $20\%$ 的数据，保证 $q_k=0$。

对于 $100\%$ 的数据，保证 $1 \le n,m \le 10^5$。

时空限制：2000ms/256MiB。