题目描述

考虑一条高铁线路 G39，这条线路依次经过 N 个火车站，编号为 1，2，3，……，n。

现在你得到了关于未来 K 天的 M 条订票信息，问你每天至少安排多少个座位可以满足这些订票信息。

每条订票信息形如 i j k, 代表在第 i 天出行，从 j 火车站上车，从 k 火车站下车。

注意座位可以重复使用，但不能两个人坐一个座位，如果一条信息是1 1 3，另一条信息是 1 3 5，那么只安排一个座位即可 (第一位乘客在 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 ≤ 100, N ≤ 100。

对于 60% 的数据， M ≤ 3000, N ≤ 3000。

对于 100% 的数据， 1 ≤ K ≤ 50, 1 ≤ M ≤ 10^6,2 ≤ N ≤ 10^6, 满足1 ≤ i ≤ K; 1 ≤ j < k ≤ N。