AT_abc464_c [ABC464C] Plumage Palette

高橋君は鳥 $ 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 $ 日目の観察で鳥の色が何種類あったかを求めてください。

入力は以下の形式で標準入力から与えられる。 > $ N $ $ M $ $ A_1 $ $ D_1 $ $ B_1 $ $ A_2 $ $ D_2 $ $ B_2 $ $ \vdots $ $ A_N $ $ D_N $ $ B_N $

$ M $ 行出力せよ。 そのうち $ j $ 行目には、 $ j $ 日目に鳥の色が何種類あったかを出力せよ。

### Sample Explanation 1 この入力では、 $ 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 $ 種類です。 ### 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 $ - 入力はすべて整数