#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
const long long LIM = 500000001LL; // cap value
int n, m, h;
if (!(cin >> n >> m >> h)) return 0;
// S[destination] = list of pairs (source, stay)
vector<vector<pair<int,int>>> S(n);
for (int i = 0; i <= n-2; ++i) {
for (int r = 0; r < h; ++r) {
int j, t;
cin >> j >> t;
// Only keep flights that go nearer to Brasilia:
// destination j must be closer => j > i (as statement defines)
if (j > i && j < n) {
S[j].emplace_back(i, t);
}
}
}
if (m == 0) return 0; // nothing to output
// f[c][d] = number of ways to reach city c in at most d nights (0 <= d < m)
vector<vector<long long>> f(n, vector<long long>(m, 0LL));
// base: being at Amman (city 0) counts as 1 way at day 0 (and by recurrence will be 1 for all d)
f[0][0] = 1;
// compute for D = 0 separately or inside loop
for (int C = 1; C < n; ++C) {
long long cur = 0;
for (auto &pr : S[C]) {
int i = pr.first;
int t = pr.second;
if (0 - t >= 0) cur += f[i][0 - t]; // only possible if t == 0
}
if (cur > LIM) cur = LIM;
f[C][0] = cur;
}
// D >= 1
for (int D = 1; D < m; ++D) {
// city 0: no incoming flights; stays 1 way (already there) so f[0][D] = f[0][D-1] (which is 1)
f[0][D] = f[0][D-1];
for (int C = 1; C < n; ++C) {
long long val = f[C][D-1]; // ways that reached C in <= D-1 and wait
for (auto &pr : S[C]) {
int i = pr.first;
int t = pr.second;
int prevD = D - t;
if (prevD >= 0) {
val += f[i][prevD];
if (val >= LIM) { val = LIM; break; }
}
}
if (val > LIM) val = LIM;
f[C][D] = val;
}
}
// destination is city n-1
vector<long long> ans(m, 0LL);
for (int D = 0; D < m; ++D) {
long long cum = f[n-1][D];
long long prev = (D == 0 ? 0LL : f[n-1][D-1]);
long long exact = cum - prev;
if (exact < 0) exact = 0; // safety (can happen if both capped)
if (exact > LIM) exact = LIM;
cout << exact << (D+1 < m ? ' ' : '\n');
}
return 0;
}
