#P18893. [2026多校联测]区间加法

[2026多校联测]区间加法

题目描述

要求你维护一个长度为 n 的序列,初始的时候全是 0。然后会进行 q 操作,每次操

作形如以下两种之一:

• 1 l r: 把 l 到 r 区间加一

• 2 l r: 把 l 到 r 这一段操作全部都做一遍。保证 r 小于这个操作的编号

请你在所有操作做完后输出这个序列对 109+710^9 + 7 取模后的结果。

温馨提示:操作 2 可以嵌套操作 2。

输入格式

第一行输入两个整数 n, q

之后 q 行,每行三个整数表示一个操作。

对于操作 1,保证 1≤l≤r≤n1 \leq l \leq r \leq n。

对于操作 2,保证 1≤l≤r<x1 \leq l \leq r < x,其中 x 表示当前是第几个操作。

输出格式

一行 n 个数字,表示最终序列对 109+710^9 + 7 取模后的结果。

样例 1 输入

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

样例 1 输出

7 7 0 7 7

样例 2 输入

10 10
1 4 9
2 1 1
2 1 1
2 1 2
2 1 2
1 5 6
2 2 5
1 3 6
2 2 3
2 4 8

样例 2 输出

0 0 2 27 29 29 25 25 25 0 

数据范围

对于 20%20\% 的数据:n,q≤10n,q \leq 10

对于 50%50\% 的数据:n,q≤103n,q \leq 10^3

对于 100%100\% 的数据:n,q≤105n,q \leq 10^5