#include <bits/stdc++.h>
using namespace std;
// Print u128 (helper)
string toStringUnsigned128(__uint128_t x) {
if (x == 0) return "0";
string s;
while (x > 0) {
int digit = (int)(x % 10);
s.push_back('0' + digit);
x /= 10;
}
reverse(s.begin(), s.end());
return s;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
const unsigned long long OUT_LIM = 500000001ULL; // output cap
const __uint128_t INTERNAL_CAP = (__uint128_t)10000000000000000000ULL; // 1e19, safe internal cap
int n, m, h;
if (!(cin >> n >> m >> h)) return 0;
// S[j] = list of flights arriving to j: pairs (from_i, stay_t)
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 strictly closer to Brasilia (j > i)
if (j > i && j < n) {
S[j].emplace_back(i, t);
}
}
}
if (m <= 0) return 0;
// dp[c][d] = number of ways to reach city c in <= d nights (cumulative), using internal big integers
vector<vector<__uint128_t>> dp(n, vector<__uint128_t>(m, 0));
// Base: at city 0 (Amman) there is exactly 1 way to be there with 0 nights (start)
dp[0][0] = 1;
// D = 0: compute for cities > 0 (only flights with t == 0 can contribute)
for (int C = 1; C < n; ++C) {
__uint128_t s = 0;
for (auto &pr : S[C]) {
int i = pr.first;
int t = pr.second;
if (0 - t >= 0) { // only t == 0
s += dp[i][0 - t];
if (s >= INTERNAL_CAP) { s = INTERNAL_CAP; break; }
}
}
dp[C][0] = s;
}
// D >= 1
for (int D = 1; D < m; ++D) {
dp[0][D] = dp[0][D-1]; // stay at Amman
for (int C = 1; C < n; ++C) {
__uint128_t val = dp[C][D-1]; // ways that were already at C and waited
for (auto &pr : S[C]) {
int i = pr.first;
int t = pr.second;
int prevD = D - t;
if (prevD >= 0) {
val += dp[i][prevD];
if (val >= INTERNAL_CAP) { val = INTERNAL_CAP; break; }
}
}
if (val >= INTERNAL_CAP) val = INTERNAL_CAP;
dp[C][D] = val;
}
}
// output exact counts for city n-1, days 0..m-1
for (int D = 0; D < m; ++D) {
__uint128_t cum = dp[n-1][D];
__uint128_t prev = (D == 0 ? (__uint128_t)0 : dp[n-1][D-1]);
__uint128_t exact = (cum >= prev ? cum - prev : 0);
unsigned long long out;
if (exact >= (__uint128_t)OUT_LIM) out = OUT_LIM;
else out = (unsigned long long)(exact);
cout << out << (D+1 < m ? ' ' : '\n');
}
return 0;
}
