#C1005. 染色
染色
当前没有测试数据。
Background
平面上有n个珠子排成一排, 每个珠子初始颜色为0,小B要对他们进行m次染色,每次选定l和r,然后把[l,r]之间的珠子染成编号c的颜色,每个珠子的最终颜色为它曾经染过的编号最大的颜色,请你写个程序统计每个珠子最终的颜色。
Input
第一行两个数n,m,表示珠子个数和染色的次数
接下来m行,每行三个数l,r,c如题意所示
Output
由于数据较大,为了减少输出所用的不必要的时间,请采取以下规则输出:
假如a[i]为第i个珠子的最终颜色
for i := 1 to n do ans := (ans * 1200007 + a[i]) mod 999911659;
输出一个数,即上述规则下的ans。
Samples
3 2
1 2 1
2 2 2
146411103
Limitation
30% n,m<=5000
50% n,m <= 10000
80% n,m <= 500000
100% n <= 1000000, m <= 2000000