题目描述

高橋君在 $M$ 天里观察了编号为 $1, 2, \ldots, N$ 的 $N$ 只鸟。

每只鸟身上都有 $1, 2, \ldots, N$ 这 $N$ 种颜色中的某一种。有趣的是，这些鸟在观察期间会变色：

• 第 $i$ 只鸟在第 $D_i - 1$ 天及以前是颜色 $A_i$；
• 从第 $D_i$ 天开始变成颜色 $B_i$。

特别地：

• 若 $D_i = 1$，则这只鸟从第 $1$ 天起就是颜色 $B_i$（也就是颜色 $A_i$ 从来没被观察到过）；
• 若 $A_i = B_i$，则这只鸟在整个观察期间颜色没有变化。

对每个 $j = 1, 2, \ldots, M$，请求出第 $j$ 天观察到的鸟一共有多少种颜色。

输入格式

N M
A_1 D_1 B_1
A_2 D_2 B_2
...
A_N D_N B_N

输出格式

输出 $M$ 行，第 $j$ 行是第 $j$ 天鸟的颜色种类数。

输入示例 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

示例 1 说明

这组数据里观察 $6$ 只鸟、共 $7$ 天。

• 第 $1$ 天，各鸟颜色依次为 $1, 2, 5, 3, 6, 6$，共 $5$ 种（第 $5$ 只鸟因为 $D_5 = 1$，一开始就是 $B_5 = 6$）。
• 第 $2$ 天，颜色为 $1, 2, 5, 3, 6, 6$，共 $5$ 种。
• 第 $3$ 天，第 $1$、$4$、$6$ 只鸟变色，颜色为 $2, 2, 5, 5, 6, 6$，共 $3$ 种（第 $6$ 只鸟 $A_6 = B_6 = 6$，其实没变）。
• 第 $4$ 天，颜色为 $2, 2, 5, 5, 6, 6$，共 $3$ 种。
• 第 $5$ 天，第 $3$ 只鸟变色，颜色为 $2, 2, 1, 5, 6, 6$，共 $4$ 种。
• 第 $6$ 天，第 $2$ 只鸟变色，颜色为 $2, 5, 1, 5, 6, 6$，共 $4$ 种。
• 第 $7$ 天，颜色为 $2, 5, 1, 5, 6, 6$，共 $4$ 种。

约束条件

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