OI XXIV - sum

// https://szkopul.edu.pl/problemset/problem/Ng815bt4Fko9lj2-l7eVl3Aw/statement/

#include <bits/stdc++.h>

// #define GARY_DBG
#define GARY_LIB

constexpr int sizik = 201;

#define ar std::array

typedef std::vector<std::vector<int>> _kra;

int s, m, q;
int64_t dp[sizik + 1][sizik + 1][sizik + 1];
int power10[sizik + 1];

constexpr int64_t INF = 1e18 + 5;

void dodaj(int64_t& a, int64_t b) {
    a += b;
    if (a > INF) a = INF;
}

std::string get_ans(int64_t k) {
    int L = -1;

    for (int i = 1; i < sizik; i++) {
        int64_t cnt = 0;

        int dx = std::min(9, s);
        for (int d = 1; d <= dx; d++) {
            dodaj(cnt, dp[i - 1][s - d][(m - ((d * power10[i - 1]) % m)) % m]);
        }

        if (k <= cnt) {
            L = i;
            break;
        }
        k -= cnt;
    }

    if (L == -1) return "NIE";

    std::string ans;
    int S = 0;
    int R = 0;
    for (int i = L - 1; i >= 0; i--) {
        int xd = (i == (L - 1)) ? 1 : 0;
        for (int d = xd; d <= 9; d++) {
            int szukana_suma = s - d - S;
            if (szukana_suma < 0) continue;
            int next_reszta = (R * 10 + d) % m;
            int szukana_reszta = (m - (next_reszta * power10[i]) % m) % m;
            int64_t cnt = dp[i][szukana_suma][szukana_reszta];
            if (k <= cnt) {
                ans.push_back(d + '0');
                S += d;
                R = next_reszta;
                break;
            } else {
                k -= cnt;
            }
        }
    }

    return ans;
}

void precompute() {
    power10[0] = 1 % m;
    for (int p = 1; p <= 200; p++) {
        power10[p] = (power10[p - 1] * 10) % m;
    }

    dp[0][0][0] = 1;
    for (int i = 0; i < sizik; i++) {
        for (int k = 0; k < m; k++) {
            for (int j = 0; j <= s; j++) {
                if (dp[i][j][k] == 0) continue;

                for (int d = 0; d <= 9; d++) {
                    if (j + d <= s) {
                        dodaj(dp[i + 1][j + d][(10 * k + d) % m], dp[i][j][k]);
                    }
                }
            }
        }
    }
}

void solve() {
    std::cin >> s >> m >> q;

    precompute();

    for (int i = 0; i < q; i++) {
        int64_t k;
        std::cin >> k;

        auto ans = get_ans(k);
        std::cout << ans << '\n';
    }
}

int32_t main() {
#ifndef GARY_DBG
    std::ios_base::sync_with_stdio(0);
    std::cin.tie(0);
    std::cout.tie(0);
#endif

    int t = 1;
    // std::cin >> t;

    for (; t > 0; t--) {
        solve();
    }

    return 0;
}