题目描述

给定一个长度为 $n$ 的序列 $a_1,a_2,\ldots,a_n$。初始值均为 $0$。

有 $m$ 次操作，每次操作选择一个区间 $[l,r]$。（定义 $\text{len}=r-l+1$）

• 令 $a_i=a_i+(i-l+1)^2$。
• 形式化的说对区间的每个数分别增加 $1^2,2^2,\ldots,\text{len}^2$。

在所有操作结束后，输出序列 $a$ 每个数字的值。由于答案可能很大，你需要对 $998244353$ 取余。

输入格式

第一行输入两个数 $n$ 和 $m$。

接下来 $m$ 行，每行输入两个整数 $l,r$。

输出格式

一行 $n$ 个数，为 $a_1 \sim a_n$。

5 3
2 2
1 3
3 5

1 5 10 4 9

提示

对于 $100\%$ 的数据，保证 $1\leq n,m\leq 10^6$，保证 $1\leq l\leq r\leq n$。

• 子任务 1（30 分）：保证 $n,m\leq 5000$。
• 子任务 2（20 分）：保证 $l=1$。
• 子任务 3（50 分）：没有特殊限制。