OI XXII - pus

// https://szkopul.edu.pl/problemset/problem/_PLjXEFyR0XMBQ-kZ1k_GgHE/site/?key=statement

#include <bits/stdc++.h>

// #define GARY_DBG
#define GARY_LIB

constexpr int sizik = 1000 * 1001, INF = 1e9, NINF = -1e9;

#define ar std::array

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

int init_val[sizik];

std::vector<std::pair<int, int>> kra[sizik];
int n, s, m;

int available = 0;

int zmp[sizik], rev_map[sizik];
int mini[sizik], val[sizik];

void build1(int v, int tl, int tr) {
    available = std::max(available, v);
    if (tl == tr) {
        zmp[tl] = v;
        rev_map[v] = tl;
    } else {
        int tm = (tl + tr) / 2;

        kra[v].push_back({2 * v, 0});
        kra[v].push_back({2 * v + 1, 0});

        build1(2 * v, tl, tm);
        build1(2 * v + 1, tm + 1, tr);
    }
}

void build_graph1() {
    return build1(1, 1, n);
}

std::vector<int> ziom;

void get1(int v, int tl, int tr, int l, int r) {
    if (l > r) return;
    if (tl == l && tr == r) {
        ziom.push_back(v);
        return;
    }
    int tm = (tl + tr) / 2;
    get1(2 * v, tl, tm, l, std::min(r, tm));
    get1(2 * v + 1, tm + 1, tr, std::max(l, tm + 1), r);
}

std::vector<int> zmapuj(std::pair<int, int> t) {
    ziom.clear();
    get1(1, 1, n, t.first, t.second);
    return ziom;
}

std::vector<int> topo_sort(int N) {
    std::vector<int> in_deg(N + 1);
    for (int i = 1; i <= N; i++) {
        for (const auto& [u, w] : kra[i]) {
            in_deg[u]++;
        }
    }
    std::queue<int> q;
    for (int i = 1; i <= N; i++) {
        if (in_deg[i] == 0) {
            q.push(i);
        }
    }
    std::vector<int> ans;
    ans.reserve(N);
    while (!q.empty()) {
        auto y = q.front();
        q.pop();
        ans.push_back(y);
        for (const auto& [u, w] : kra[y]) {
            if (--in_deg[u] == 0) {
                q.push(u);
            }
        }
    }
    if ((int)ans.size() != N) {
        return {};
    }
    return ans;
}

void solve() {
    ziom.reserve(sizik);

    std::cin >> n >> s >> m;

    for (int i = 1; i <= s; i++) {
        int p, d;
        std::cin >> p >> d;

        init_val[p] = d;
    }

    build_graph1();

    for (int i = 1; i <= m; i++) {
        int l, r, k;
        std::cin >> l >> r >> k;
        std::vector<int> x(k);
        for (auto& a : x) {
            std::cin >> a;
        }

        int prev = l;
        std::vector<std::pair<int, int>> sg;
        sg.reserve(k);
        x.push_back(r + 1);
        for (const auto& a : x) {
            if (a == prev) {
                prev++;
            } else {
                assert(prev < a);
                sg.push_back({prev, a - 1});
                prev = a + 1;
            }
        }
        x.pop_back();

        int meta = ++available;
        for (const auto& t : sg) {
            auto z = zmapuj(t);
            for (const auto& y : z) {
                kra[meta].push_back({y, 0});
            }
        }
        for (const auto& y : x) {
            kra[zmp[y]].push_back({meta, 1});
        }
    }

    auto kol = topo_sort(available);

    if (kol.empty()) {
        std::cout << "NIE\n";
        return;
    }

    for (int i = 0; i <= available; i++) {
        mini[i] = INF;
        val[i] = NINF;
    }

    bool isGood = true;

    for (const auto& a : kol) {
        val[a] = mini[a];
        if (val[a] < 1) {
            isGood = false;
            break;
        }
        if (rev_map[a] > 0 && init_val[rev_map[a]] > 0) {
            if (init_val[rev_map[a]] > val[a]) {
                isGood = false;
                break;
            }
            val[a] = init_val[rev_map[a]];
        }
        for (const auto& [u, w] : kra[a]) {
            mini[u] = std::min(mini[u], val[a] - w);
        }
    }

    if (!isGood) {
        std::cout << "NIE\n";
        return;
    }

    std::cout << "TAK\n";
    for (int i = 1; i <= n; i++) {
        std::cout << val[zmp[i]] << ' ';
    }
    std::cout << '\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;
}