C - Plumage Palette 解説 /

実行時間制限: 2 sec / メモリ制限: 1024 MiB

配点 : 300 点

問題文

高橋君は鳥 1,2,\dots,N の N 羽の鳥を M 日間観察しました。
高橋君が観察した鳥には色 1,2,\dots,N の N 色のうちいずれか 1 色がついていますが、これらの鳥には観察期間中に色が変化するという興味深い特徴があります。

鳥 i は D_i-1 日目以前の観察では色 A_i であり、 D_i 日目以降の観察では色 B_i になりました。
ただし、 D_i=1 である場合はその鳥の色は 1 日目の観察から B_i であり、 A_i=B_i である場合はその鳥の色は観察期間中に変化しませんでした。

j=1,2,\dots,M について、 j 日目の観察で鳥の色が何種類あったかを求めてください。

制約

  • 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
  • 入力はすべて整数

入力

入力は以下の形式で標準入力から与えられる。

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

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 種類です。

Score : 300 points

Problem Statement

Takahashi observed N birds, numbered 1, 2, \dots, N, over M days.
Each of the birds that Takahashi observed has one of N colors, numbered 1, 2, \dots, N, and these birds have an interesting characteristic: their color can change during the observation period.

Bird i had color A_i in observations on or before day D_i - 1, and color B_i in observations on or after day D_i.
Here, if D_i = 1, then the bird's color was B_i from the observation on day 1, and if A_i = B_i, then the bird's color did not change during the observation period.

For each j = 1, 2, \dots, M, find the number of different colors of birds on day j.

Constraints

  • 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
  • All input values are integers.

Input

The input is given from Standard Input in the following format:

N M
A_1 D_1 B_1
A_2 D_2 B_2
\vdots
A_N D_N B_N

Output

Output M lines.
The j-th line should contain the number of different colors of birds on day j.

Sample Input 1

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

Sample Output 1

5
5
3
3
4
4
4

In this input, six birds are observed over seven days.

  • On day 1, the color of each bird was 1, 2, 5, 3, 6, 6. There are 5 different colors in total.
  • On day 2, the color of each bird was 1, 2, 5, 3, 6, 6. There are 5 different colors in total.
  • On day 3, the color of each bird was 2, 2, 5, 5, 6, 6. There are 3 different colors in total.
  • On day 4, the color of each bird was 2, 2, 5, 5, 6, 6. There are 3 different colors in total.
  • On day 5, the color of each bird was 2, 2, 1, 5, 6, 6. There are 4 different colors in total.
  • On day 6, the color of each bird was 2, 5, 1, 5, 6, 6. There are 4 different colors in total.
  • On day 7, the color of each bird was 2, 5, 1, 5, 6, 6. There are 4 different colors in total.