首先对原图形进行变换。原问题等价于：

给定平面上 $n$ 个等腰直角三角形，第 $i$ 个三角形顶点分别为 $(x_i, y_i), (x_i + z_i, y_i), (x_i, y_i + z_i)$，对每个 $k \in [1, K]$，求被覆盖至少 $k$ 次的面积总和。

考虑按照 $x_i + y_i + z_i$ 从大到小扫描线，相当于有一条斜率为 $-1$ 的直线从右往左去截已经加入的三角形。所以截的过程中，可以把每个已加入的三角形看成 $[x_i, +\infty) \times [y_i, +\infty)$ 的右上矩形。

由于单调性，我们可以对每个 $k \in [1, K]$，维护分段函数 $f_k(x)$ 表示当前 $[x, x + 1)$ 这一段，$y \ge f_k(x)$ 的部分都被覆盖至少 $k$ 次，在平面上就是阶梯状物。

加入一个三角形时，若 $k = 1$，相当于 $x \ge x_i, f_1(x) \gets \min(f_1(x), y_i)$，参考官方题解的一张图：

我们希望把“旧的至少覆盖 $1$ 次的区域”和“新矩形”取交，把交的部分传给 $k = 2$。所以我们把更新前的 $f_1(x) \ge y_i$ 的段拿出来，取更新前的值，拼上结尾可能剩下的新矩形值为 $y_i$ 的一段，把这些段扔到 $k = 2$ 继续类似地做。

所以我们的流程是，对每个 $k$ 会传进去一些段 $[l, r)$，值为 $v$，表示 $x \in [l, r), f_k(x) \gets \min(f_k(x), v)$。然后把传入的区域和旧的被覆盖 $\ge k$ 次区域取交，也就是把每次更新前 $f_k(x) \ge v$ 的段拿出来，取更新前的值，拼上结尾可能剩下的新矩形值为 $y_i$ 的一段，传给 $k + 1$ 继续做。初始 $k = 1$ 传入的段是 $[x_i, +\infty)$，值为 $y_i$。

维护分段函数可以用连续段均摊技巧。算面积就差分一下，减去每一段原来的，加上更新后的。

由于每次所有 $f_k(x)$ 最多增加 $O(K)$ 个段，所以所有层的总段数始终只有 $O(nK)$，每次分段函数取 $\min$ 处理的段数和总段数成正比，所以总时间复杂度 $O(nK \log n)$。

:::info[代码]

#include <bits/stdc++.h>
#define pb emplace_back
#define fst first
#define scd second
#define mkp make_pair
#define mems(a, x) memset((a), (x), sizeof(a))

using namespace std;
using ll = long long;
using ull = unsigned long long;
using db = double;
using ldb = long double;
using pii = pair<int, int>;
using pll = pair<ll, ll>;

namespace IO {
	const int maxn = 1 << 20;
	
	char ibuf[maxn], *iS, *iT, obuf[maxn], *oS = obuf;

	inline char gc() {
		return (iS == iT ? iT = (iS = ibuf) + fread(ibuf, 1, maxn, stdin), (iS == iT ? EOF : *iS++) : *iS++);
	}

	template<typename T = int>
	inline T read() {
		char c = gc();
		T x = 0;
		bool f = 0;
		while (c < '0' || c > '9') {
			f |= (c == '-');
			c = gc();
		}
		while (c >= '0' && c <= '9') {
			x = (x << 1) + (x << 3) + (c ^ 48);
			c = gc();
		}
		return f ? ~(x - 1) : x;
	}
	
	inline int reads(char *s) {
		char c = gc();
		int len = 0;
		while (isspace(c)) {
			c = gc();
		}
		while (!isspace(c) && c != EOF) {
			s[len++] = c;
			c = gc();
		}
		s[len] = '\0';
		return len;
	}
	
	inline string reads() {
		char c = gc();
		string s;
		while (isspace(c)) {
			c = gc();
		}
		while (!isspace(c) && c != EOF) {
			s += c;
			c = gc();
		}
		return s;
	}

	inline void flush() {
		fwrite(obuf, 1, oS - obuf, stdout);
		oS = obuf;
	}
	
	struct Flusher {
		~Flusher() {
			flush();
		}
	} AutoFlush;

	inline void pc(char ch) {
		if (oS == obuf + maxn) {
			flush();
		}
		*oS++ = ch;
	}
	
	inline void write(char *s) {
		for (int i = 0; s[i]; ++i) {
			pc(s[i]);
		}
	}
	
	inline void write(const char *s) {
		for (int i = 0; s[i]; ++i) {
			pc(s[i]);
		}
	}

	template<typename T>
	inline void write(T x) {
		static char stk[64], *tp = stk;
		if (x < 0) {
			x = ~(x - 1);
			pc('-');
		}
		do {
			*tp++ = x % 10;
			x /= 10;
		} while (x);
		while (tp != stk) {
			pc((*--tp) | 48);
		}
	}
	
	template<typename T>
	inline void writesp(T x) {
		write(x);
		pc(' ');
	}
	
	template<typename T>
	inline void writeln(T x) {
		write(x);
		pc('\n');
	}
}

using IO::read;
using IO::reads;
using IO::write;
using IO::pc;
using IO::writesp;
using IO::writeln;

const int maxn = 200100;

ll n, m, K, ans[9];

struct tri {
	ll x, y, z;
} a[maxn];

struct node {
	ll l, r, x;
	node(ll _l = 0, ll _r = 0, ll _x = 0) : l(_l), r(_r), x(_x) {}
};

inline bool operator < (const node &a, const node &b) {
	return a.l < b.l || (a.l == b.l && a.r < b.r);
}

struct DS {
	set<node> S;
	
	inline void init() {
		S.emplace(0, m - 1, m);
	}
	
	inline auto split(ll p) {
		if (p == m) {
			return S.end();
		}
		auto it = S.lower_bound(node(p));
		if (it != S.end() && it->l == p) {
			return it;
		}
		node u = *(--it);
		S.erase(it);
		S.emplace(u.l, p - 1, u.x);
		return S.emplace(p, u.r, u.x).fst;
	}
	
	inline vector<node> update(ll l, ll r, ll x) {
		auto itr = split(r + 1), itl = split(l);
		vector<node> vc;
		r = l - 1;
		for (auto it = itl; it != itr; it = S.erase(it)) {
			if (it->x >= x) {
				r = it->r;
				vc.pb(*it);
			} else {
				break;
			}
		}
		if (l <= r) {
			S.emplace(l, r, x);
		}
		return vc;
	}
} T[9];

void solve() {
	m = read();
	n = read();
	K = read();
	for (int i = 1; i <= n; ++i) {
		a[i].x = read();
		a[i].y = read();
		a[i].z = read();
	}
	sort(a + 1, a + n + 1, [&](const tri &a, const tri &b) {
		return a.x + a.y + a.z > b.x + b.y + b.z;
	});
	auto calc = [&](ll x, ll y, ll z) -> ll {
		z -= x + y;
		return z < 0 ? 0 : z * z;
	};
	for (int i = 1; i <= K; ++i) {
		T[i].init();
	}
	for (int i = 1; i <= n; ++i) {
		vector<node> vc;
		vc.pb(a[i].x, m - 1, a[i].y);
		ll z = a[i].x + a[i].y + a[i].z;
		for (int k = 1; k <= K; ++k) {
			vector<node> nv;
			for (node u : vc) {
				if (u.x == m) {
					nv.pb(u);
					continue;
				}
				auto ds = T[k].update(u.l, u.r, u.x);
				for (node v : ds) {
					nv.pb(v);
					ans[k] -= calc(v.l, v.x, z) - calc(v.r + 1, v.x, z);
					ans[k] += calc(v.l, u.x, z) - calc(v.r + 1, u.x, z);
				}
			}
			ll x = (nv.size() ? nv.back().r + 1 : a[i].x);
			if (x < m) {
				nv.pb(x, m - 1, a[i].y);
			}
			vc = move(nv);
		}
	}
	for (int i = 1; i <= K; ++i) {
		writeln(ans[i]);
	}
}

int main() {
	int T = 1;
	// scanf("%d", &T);
	while (T--) {
		solve();
	}
	return 0;
}

:::