#XMOJ12269. 多人涂色比赛

多人涂色比赛

说明

时间限制:3 Sec 内存限制:256 MB 输入文件:color.in 输出文件:color.out

玩家分为 A、B、C、D、E 五支队伍,用代表各自队伍的颜色对同一个数组进行涂色争夺。

最终得分等于被本队颜色涂过的元素数量加上后文所述奖励分,得分最高的队伍获胜。

规则

1. 给定长度为 $N$ 的数组,初始全部未被涂色。也就是说,所有位置上各个颜色的厚度都是 $0$。

2. 五支队伍可以选择数组区间 $[l,r]$,用自己队伍的颜色进行涂色:

   - 如果该位置完全没有被涂过:涂上本队颜色,本队颜色厚度变为 $1$。

   - 如果该位置已经是本队颜色:本队颜色厚度 $+1$。

   - 如果该位置是别的队伍颜色:被本次颜色覆盖,其他队伍厚度清零,本队厚度置为 $1$。

3. 游戏会不定期触发奖励机会。

   - 奖励机会给出区间 $[l,r]$,设区间 $[l,r]$ 内队伍X的颜色厚度总和为 $X_{lr}$($X=A,B,C,D,E$)。

   - 如果有且仅有一支队伍的 $X_{lr}$ 是最大值,则给这支队伍加上 $\max(A_{lr},B_{lr},C_{lr},D_{lr},E_{lr})$ 的奖励分。

   - 如果最大值存在并列,则任何队伍都得不到奖励分。

4. 游戏结束时,每支队伍的总得分 = 整个数组 $[0,N-1]$ 上本队颜色厚度总和 + 累计得到的奖励分。

游戏已经结束,只需要计算最终分数。按时间顺序给出所有队伍操作和奖励机会,请输出五支队伍的最终得分。

输入格式

第一行一个整数 $N$。

第二行一个整数 $Q$。

接下来 $Q$ 行,每行三个整数 $x_k,l_k,r_k$。

- $x_k=0$:区间 $[l_k,r_k]$ 的奖励机会

- $x_k=1$:队伍 A 对区间 $[l_k,r_k]$ 涂色

- $x_k=2$:队伍 B 对区间 $[l_k,r_k]$ 涂色

- $x_k=3$:队伍 C 对区间 $[l_k,r_k]$ 涂色

- $x_k=4$:队伍 D 对区间 $[l_k,r_k]$ 涂色

- $x_k=5$:队伍 E 对区间 $[l_k,r_k]$ 涂色

输出格式

输出队伍 A、B、C、D、E 的得分,每个分数对 $10^{18}+9$ 取模,用空格隔开。

样例

样例 1

5
2
1 0 3
2 2 4

2 3 0 0 0

样例 2

5
3
1 0 4
2 1 3
0 4 4

3 3 0 0 0

样例 3

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

10 1 0 0 0

数据范围

对于 100% 的数据,$1 \leq N \leq 10^{13}$,$0 \leq Q \leq 1.5\times 10^5$,$0 \leq x_k \leq 5$,$0 \leq l_k \leq r_k \lt N$。