#include <algorithm>
#include <cassert>
#include <iostream>
#include <numeric>
#include <set>
#include <tuple>
#include <vector>
using namespace std;
template <typename T>
using vc = vector<T>;
using ll = long long;
#define eb emplace_back
#define all(x) (x).begin(), (x).end()
#define len(x) ll((x).size())
#define FOR(i, a, b) for (ll i = (a); i < (b); ++i)
template <typename T>
vc<int> argsort(const vc<T> &A) {
vc<int> ids(len(A));
iota(all(ids), 0);
sort(all(ids),
[&](int i, int j) { return (A[i] == A[j] ? i < j : A[i] < A[j]); });
return ids;
}
template <typename T>
vc<T> rearrange(const vc<T> &A, const vc<int> &I) {
vc<T> B(len(I));
FOR(i, 0, len(I)) B[i] = A[I[i]];
return B;
}
/*
定数区間管理で単調減少列を扱う
*/
struct S {
int N;
set<int> cut;
vc<int> A;
// 最初は INF で初期化
S(int N, int init_val) : N(N), A(N) {
cut.insert(0), cut.insert(N);
A[0] = init_val;
}
// <= k
int prev(int k) {
auto it = cut.lower_bound(k + 1);
if (it == cut.begin()) return -1;
return *(::prev(it));
}
// >= k
int next(int k) {
auto it = cut.lower_bound(k);
if (it == cut.end()) return N + 1;
return *(it);
}
// L,...,R-1 を chmin(v)
// return: 変更前の値
vc<tuple<int, int, int>> chmin(int L, int R, int v) {
split(L), split(R);
if (A[L] <= v) return {};
int p = L;
vc<tuple<int, int, int>> rm;
while (p < R && A[p] > v) {
cut.erase(p);
int q = next(p);
rm.eb(p, q, A[p]);
p = q;
}
cut.insert(L);
A[L] = v;
return rm;
}
void split(int k) {
if (cut.count(k)) return;
int l = prev(k);
A[k] = A[l];
cut.insert(k);
}
// vc<int> get_all() {
// vc<int> B(N);
// int v = A[0];
// FOR(i, N) {
// if (cut[i]) ::chmin(v, A[i]);
// B[i] = v;
// }
// return B;
// }
};
const int INF = 1'010'000'000;
void solve() {
ll L, N, K;
cin >> L >> N >> K;
vc<tuple<ll, ll, ll>> tri(N);
FOR(i, 0, N) {
ll a, b, c;
cin >> a >> b >> c;
tri[i] = {a, b, c};
}
// a, b を座圧, distinct になるようにする
vc<ll> X, Y;
{
FOR(i, 0, N) X.eb(get<0>(tri[i]));
auto I = argsort(X);
FOR(i, 0, N) { get<0>(tri[I[i]]) = i; }
X = rearrange(X, I);
}
{
FOR(i, 0, N) Y.eb(get<1>(tri[i]));
auto I = argsort(Y);
FOR(i, 0, N) { get<1>(tri[I[i]]) = i; }
Y = rearrange(Y, I);
}
// a+b+d について降順
sort(all(tri), [&](auto &T1, auto &T2) -> bool {
auto [a1, b1, d1] = T1;
auto [a2, b2, d2] = T2;
return X[a1] + Y[b1] + d1 > X[a2] + Y[b2] + d2;
});
vc<ll> ANS(K + 1);
// [x1,x2]x[y,inf] のうち x+y<=t を満たす部分
// 渡すのは座圧インデックス
auto calc = [&](ll x1, ll x2, ll y, ll t) -> ll {
x1 = X[x1];
x2 = X[x2];
y = Y[y];
t -= y;
if (t <= 0) return 0;
auto f = [&](ll x) -> ll {
ll ans = 0;
ans += t * t;
if (x <= t) ans -= (t - x) * (t - x);
return ans;
};
return f(x2) - f(x1);
};
FOR(i, 0, K + 1) X.eb(INF), Y.eb(INF);
// k 枚以上であるところ
vc<S> dat;
FOR(k, 0, K + 1) {
int ini = (k == 0 ? 0 : N + k);
dat.eb(S(N, ini));
}
for (auto &[a, b, d] : tri) {
ll t = X[a] + Y[b] + d;
vc<tuple<int, int, int>> rect;
rect.eb(a, N, b);
FOR(k, 1, K + 1) {
vc<tuple<int, int, int>> nxt;
for (auto &[l, r, v] : rect) {
auto rm = dat[k].chmin(l, r, v);
for (auto &[l1, r1, w] : rm) {
nxt.eb(l1, r1, w);
assert(w > v);
ANS[k] -= calc(l1, r1, w, t);
ANS[k] += calc(l1, r1, v, t);
}
}
int e = (nxt.empty() ? a : get<1>(nxt.back()));
if (e < N) nxt.eb(e, N, b);
swap(rect, nxt);
}
}
FOR(k, 1, K + 1) cout << ANS[k] << "\n";
}
signed main() {
cin.tie(nullptr);
ios_base::sync_with_stdio(false);
solve();
}
