// https://szkopul.edu.pl/problemset/problem/8ysq4JJXJ8Ol08M8cn36UmkM/site/?key=statement

#include <bits/stdc++.h>

using namespace std;

#define int long long

std::string to_bin(int x) {
    std::string r(5, '0');

    for (int i = 0; i < r.size(); i++) {
        r[i] = (x & 1) + '0';
        x >>= 1;
    }

    std::reverse(r.begin(), r.end());

    return r;
}

constexpr int sizik = 10 * 1001, sizik2 = 12, MAXA = 1000 * 1000 * 1000 + 1;
constexpr int sizik3 = (1 << (sizik2 - 2)) + 12, INF = INT32_MAX;

#define ar std::array
#define pr std::pair
#define vec std::vector

typedef vec<vec<int>> _kra;

int n, m, d, k;

int kpo[sizik][sizik2];
std::vector<std::pair<int, int>> kra[sizik];
int ans[sizik2];
int odl[sizik][sizik3][2];

bool BFS(int curr, int value, int num_arr) {
    int yc = (1 << curr) - 1;

    for (int i = 0; i <= n; i++) {
        for (int j = 0; j <= yc; j++) {
            odl[i][j][num_arr] = INF;
        }
    }

    std::queue<ar<int, 3>> q;
    int start_v1 = num_arr == 0 ? 1 : n;
    q.push({start_v1, 0});
    while (!q.empty()) {
        auto [v, s, d1] = q.front();
        q.pop();

        if (odl[v][s][num_arr] != INF || ((odl[v][s][num_arr] != INF) && (odl[v][s][num_arr] >= d))) {
            continue;
        }

        odl[v][s][num_arr] = d1;

        for (const auto& [u, w] : kra[v]) {
            int z = 0;
            for (int j = 0; j + 1 < curr; j++) {
                if (kpo[w][j + 1] >= ans[j + 1]) {
                    z |= (1 << j);
                }
            }
            q.push({u, s | z, d1 + 1});
        }
    }

    int wx = odl[n][yc][num_arr];
    return wx > 0 && wx <= d;
}

void solve() {
    std::cin >> n >> m >> d >> k;

    for (int i = 1; i <= m; i++) {
        int a, b;
        std::cin >> a >> b;

        kra[a].push_back({b, i});
        kra[b].push_back({a, i});

        kpo[i][0] = a;
        for (int j = 1; j <= k; j++) {
            int c;
            std::cin >> c;

            kpo[i][j] = c;
        }
        kpo[i][k + 1] = b;
    }

    for (int i = 1; i <= k; i++) {
        BFS(i, 0, 0);
        BFS(i, 0, 1);

        int xp = (1 << (i - 1)) - 1;

        vector<vector<int>> masks_by_popcount(k + 1);

        for (int s = 0; s <= xp; ++s) {
            int cnt = __builtin_popcount(s);
            masks_by_popcount[cnt].push_back(s);
        }

        for (int j = 1; j <= n; j++) {
            for (int cnt = i - 1; cnt >= 0; --cnt) {
                for (int l : masks_by_popcount[cnt]) {
                    for (int x = 0; x < i - 1; ++x) {
                        odl[j][l][1] = std::min(odl[j][l][1], odl[j][l | (1 << x)][1]);
                    }
                }
            }
        }

        for (int j = 1; j <= m; j++) {
            int z = 0;
            for (int o = 0; o + 1 < i; o++) {
                if (kpo[j][o + 1] >= ans[o + 1]) {
                    z |= (1 << o);
                }
            }

            int u = kpo[j][0], v = kpo[j][k + 1];

            for (int l = xp; l >= 0; l--) {
                if (odl[u][l][0] + odl[v][(xp ^ l) & ~z][1] + 1 <= d) {
                    ans[i] = std::max(ans[i], kpo[j][i]);
                }
            }
        }
        for (int j = 1; j <= m; j++) {
            int z = 0;
            for (int o = 0; o + 1 < i; o++) {
                if (kpo[j][o + 1] >= ans[o + 1]) {
                    z |= (1 << o);
                }
            }

            int v = kpo[j][0], u = kpo[j][k + 1];

            for (int l = xp; l >= 0; l--) {
                if (odl[u][l][0] + odl[v][(xp ^ l) & ~z][1] + 1 <= d) {
                    ans[i] = std::max(ans[i], kpo[j][i]);
                }
            }
        }
    }

    for (int i = 1; i <= k; i++) {
        std::cout << ans[i] << " ";
    }
    std::cout << '\n';
}

int32_t main() {
    std::ios_base::sync_with_stdio(0);
    std::cin.tie(0);
    std::cout.tie(0);

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

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

    return 0;
}