为了抗击 COVID-19 疫情，必须高效地将疫苗运送给民众。在 RUN-land，有 $n$ 个疫苗制造商（编号为 $1$ 到 $n$）、$m$ 所医院（编号为 $1$ 到 $m$）以及 $k$ 个代理人（编号为 $1$ 到 $k$）。代理人负责将疫苗从制造商运送到医院。第 $i$ 个代理人的任务是从制造商 $a_i$ 运送 $c_i$ 剂疫苗到医院 $b_i$。任务的设计保证任意两个代理人不会被分配到相同的制造商且相同的医院（即他们必须被分配到不同的制造商，或不同的医院，或两者都不同）。

RUN-land 有一条非常重要的法律：任何制造商最多只能雇用一名代理人，且任何医院最多只能从一名代理人处接收疫苗。可能并非所有代理人都会被召集来完成他们的任务。

代理人在抗击疫情的战斗中发挥着重要作用。因此，应该根据他们的功绩给予合理的奖励。被称为 Vickery-Clarke-Groves 定价的原则规定了每个代理人的社会价值如下：给定参与代理人的集合 $S$，令 $f(S)$ 表示在遵守上述法律的前提下，能够运送到医院的疫苗的最大可能数量。令 $U$ 为所有代理人的集合。那么每个代理人 $e$ 的社会价值为 $f(U) - f(U \setminus \{e\})$。

简而言之，假设代理人总是以最大化运送疫苗数量的方式行动，那么代理人的社会价值就对应于该代理人不参与时，运送疫苗数量的减少量。

请计算所有代理人的社会价值。

输入格式

第一行包含三个整数 $n$、$m$ 和 $k$（$1 \le n, m \le 2\,000$，$1 \le k \le \min(8\,000, n \times m)$）。

接下来的 $k$ 行，每行包含三个整数 $a_i$、$b_i$ 和 $c_i$（$1 \le a_i \le n$，$1 \le b_i \le m$，$1 \le c_i \le 10^{12}$）。

如果 $i \ne j$，则 $(a_i, b_i) \ne (a_j, b_j)$。

输出格式

输出 $k$ 行，其中第 $i$ 行包含一个整数，表示代理人 $i$ 的社会价值。

样例

输入样例 1

5 5 7
1 4 3
5 1 7
2 2 8
3 5 2
4 3 8
2 3 6
5 4 9

输出样例 1

1
1
8
2
8
0
0