题目描述

一条高铁线路 $\tt G39$ 依次经过 $n$ 个火车站，编号$1 \sim n$，现在有未来 $K$ 天的 $m$ 条的订票信息。请问每次安排至少多少座位可满足订票信息。

信息形式为“i j k”,表示第 $i$ 天出行，从 $j$ 上车，从 $k$ 下车。座位可同时使用，但两人不可同时占用同一座位（比如第一位乘客在 $3$ 号站下车，同时第二位乘客在 $3$ 号火车站上车，这样只需要一个座位即可）。

输入格式

一行数 $n，m，K$。

接下来 $m$ 行，每行三个整数 “i j k”。

输出格式

$K$ 行，每行一个整数，表示当天要多少座位。

输入输出样例

10 5 3
1 1 3
1 3 5
2 1 4
1 7 8
2 2 10

1
2
0

说明 / 提示

数据范围

• $30\%$ 数据，$m \le 100,n \le 100$;
• $60\%$ 数据，$m \le 3,000,n \le 3,000$;
• $100\%$ 数据，$1 \le K \le 50,1 \le m \le 10^6,2 \le n \le 10^6$