Plumage Palette

题目描述

小青在连续 $M$ 天内观察了编号为 $1,2,\ldots,N$ 的 $N$ 只鸟。

小青观察到的每只鸟都具有颜色 $1,2,\ldots,N$ 中的某一种颜色。特别的是，这些鸟的颜色可能会在观察期间发生变化。

对于第 $i$ 只鸟：

• 在第 $D_i-1$ 天及以前，它的颜色为 $A_i$；
• 从第 $D_i$ 天开始，它的颜色变为 $B_i$。

特别地：

• 如果 $D_i=1$，那么这只鸟从第 $1$ 天开始颜色就是 $B_i$；
• 如果 $A_i=B_i$，那么这只鸟在整个观察期间颜色都不会发生变化。

对于每一天 $j=1,2,\ldots,M$，请你求出当天所有鸟一共出现了多少种不同的颜色。

输入格式

输入从标准输入读入，格式如下：

$N M$

$A_1 D_1 B_1$

$A_2 D_2 B_2$

$\vdots$

$A_N D_N B_N$

输出格式

输出 $M$ 行。

其中，第 $j$ 行输出第 $j$ 天所有鸟一共出现了多少种不同的颜色。

输入输出样例 #1

输入 #1

6 7
1 3 2
2 6 5
5 5 1
3 3 5
4 1 6
6 3 6

输出 #1

5
5
3
3
4
4
4

样例说明

在该样例中，共观察 $6$ 只鸟，观察时间为 $7$ 天。

• 第 $1$ 天，各只鸟的颜色依次为 $1,2,5,3,6,6$，共有 $5$ 种不同的颜色。
• 第 $2$ 天，各只鸟的颜色依次为 $1,2,5,3,6,6$，共有 $5$ 种不同的颜色。
• 第 $3$ 天，各只鸟的颜色依次为 $2,2,5,5,6,6$，共有 $3$ 种不同的颜色。
• 第 $4$ 天，各只鸟的颜色依次为 $2,2,5,5,6,6$，共有 $3$ 种不同的颜色。
• 第 $5$ 天，各只鸟的颜色依次为 $2,2,1,5,6,6$，共有 $4$ 种不同的颜色。
• 第 $6$ 天，各只鸟的颜色依次为 $2,5,1,5,6,6$，共有 $4$ 种不同的颜色。
• 第 $7$ 天，各只鸟的颜色依次为 $2,5,1,5,6,6$，共有 $4$ 种不同的颜色。

数据范围

• $1\leq N\leq 3\times 10^5$
• $1\leq M\leq 3\times 10^5$
• $1\leq A_i,B_i\leq N$
• $1\leq D_i\leq M$
• 输入的所有数值均为整数

From 464C