F: 友達探し

問題

$1$ から $N$ までの番号が付けられた $N$ 人の人に対して，ある部屋の入退室記録が $M$ 個与えられる．
$i$ 番目の入退室記録は $A_i\ B_i\ C_i$ の $3$ つの整数からなり，これは以下を示している．

• $C_i = 1$ のとき，時刻 $A_i$ に $B_i$ さんが部屋に入室したことを表す.
• $C_i = 0$ のとき，時刻 $A_i$ に $B_i$ さんが部屋から退室したことを表す.

$i$ 番目($1 \leq i \leq N$)の人について，時刻 $T$ までに部屋で一緒に過ごした時間が最も長い人を答えよ．

制約

• 入力値は全て整数である.
• $2 \leq N,\ M \leq 10^5$
• $1 \leq T \leq 10^9$
• $1 \leq A_i \leq T$
• $A_i \leq A_{i+1}$
• $1 \leq B_i \leq N$
• $(A_i = A_j$ かつ $B_i = B_j$) ならば $i=j$
• $0 \leq C_i \leq 1$
• 時刻 $0$ には部屋に誰もいない
• 入退室が矛盾する入力は与えられない
• 部屋に $100$ 人より多くの人がいることはない

入力形式

入力は以下の形式で与えられる.

$N\ M\ T$
$A_1\ B_1\ C_1$
…
$A_M\ B_M\ C_M$

出力

$i$ 行目には $i$ 番目の人について，時刻 $T$ までに部屋で一緒に過ごした時間が最も長い人を出力する．
ただし，自分以外で一緒に過ごした時間が最も長い人が複数人いる場合は，最も小さい番号の人を出力せよ．
また，各行の末尾に改行を出力せよ．

サンプル

サンプル入力 1

3 6 10
1 1 1
2 2 1
4 3 1
5 1 0
6 2 0
6 3 0

サンプル出力 1

2
1
2

サンプル入力 2

3 2 5
1 1 1
2 2 1

サンプル出力 2

2
1
1

$3$ 番目の人は，$1$ 番目の人とも $2$ 番目の人とも一緒にいた時間が $0$ なので，最も小さい $1$ を出力する.