题目描述

小明有一个长度为 $n$ 的数组 $a_1,a_2,...,a_n$ ，初始全为 $0$ ，小明要对数组做 $m$ 次操作，每次操作格式如下。

选择一个长度为 $len$ 的区间 $[L,R]$ ， $1 \le L \le R \le n,(R-L+1)=len$ ，对于区间中的每一个数 $a_i ( L \le i \le R)$ ，令 $a_i=a_i+(i-L+1)^2$ 。

即对这个区间的每个数分别增加 $1^2,2^2,...,len^2$ 。

小明想知道经过 $m$ 次操作后，数组中每个数字的值。

由于结果较大，你只需要求出每个值在模 $998244353$ 意义下的结果即可。

输入格式

第一行两个整数 $n,m$ 。

加下来 $m$ 行，每行两个整数 $L,R$ ，表示对区间 $[L,R]$ 进行一次操作。

输出格式

输出一行 $n$ 个整数，表示经过 $m$ 次操作后的数组 $a_1,a_2,...,a_n$ 。

你只需要输出每个值在模 $998244353$ 意义下的结果即可。

输入输出样例 #1

输入 #1

5 3
2 2
1 3
3 5

输出 #1

1 5 10 4 9

说明/提示

对于 $30\%$ 的数据， $n,m \le 5 \times 10^3$

对于另外 $30\%$ 的数据， $n,m \le 5 \times 10^4$ 。

对于全部数据， $1 \le n,m \le 10^6, 1 \le L \le R \le n$ 。