#include<bits/stdc++.h>


using namespace std;
const int N = 1e6 + 5, LG = 21;
vector<int> c[LG];

void SA(string &s) {
    s += '$';
    int n = (int) s.size();
    vector<int> p(n);
    auto sort_ = [&](int k) {
        vector<int> cnt(n);
        for (int x: c[k]) {
            cnt[x]++;
        }
        vector<int> p_new(n), pos(n);
        pos[0] = 0;
        for (int i = 1; i < n; i++) {
            pos[i] = pos[i - 1] + cnt[i - 1];
        }
        for (int x: p) {
            p_new[pos[c[k][x]]] = x;
            pos[c[k][x]]++;
        }
        p.swap(p_new);
    };

    vector<pair<char, int>> a(n);

    for (int i = 0; i < n; i++) {
        a[i] = {s[i], i};
    }

    sort(a.begin(), a.end());

    for (int i = 0; i < n; i++) {
        p[i] = a[i].second;
    }
    c[0].resize(n);
    c[0][p[0]] = 0;
    for (int i = 1; i < n; i++) {
        c[0][p[i]] = c[0][p[i - 1]] + (a[i].first != a[i - 1].first);
    }
    for (int k = 0; (1 << k) < n; k++) {
        for (int i = 0; i < n; i++) {
            p[i] = (p[i] - (1 << k) + n) % n;
        }
        sort_(k);
        vector<int> c_new(n);
        c_new[p[0]] = 0;
        for (int i = 1; i < n; i++) {
            pair<int, int> pr = {c[k][p[i - 1]], c[k][(p[i - 1] + (1 << k)) % n]};
            pair<int, int> cur = {c[k][p[i]], c[k][(p[i] + (1 << k)) % n]};
            c_new[p[i]] = c_new[p[i - 1]] + (pr != cur);
        }
        c[k + 1] = c_new;

    }
    s.pop_back();
}

int lg[N];
int sz;

int comp(int i, int j, int l) {
    int k = lg[l];
    if (!l)return 0;
    pair<int, int> a = {c[k][i], c[k][i + l - 1 - (1 << k)]};
    pair<int, int> b = {c[k][j], c[k][j + l - 1 - (1 << k)]};
    return (a == b ? 0 : a < b ? -1 : 1);
}

pair<int, int> mat[605][605];

bool comp(vector<int> v1, vector<int> &v2, int to) {
    v1.push_back(to);
    int p1 = 1, p2 = 1;
    auto[l1, len1] = mat[v1[p1 - 1]][v1[p1]];
    auto[l2, len2] = mat[v2[p2 - 1]][v2[p2]];
    while (p1 < v1.size() && p2 < v2.size()) {
        int len = min(len1, len2);
        int ret = comp(l1, l2, len);
        if (ret != 0)
            return ret == -1;
        if (len1 < len2) {
            p1++;
            if (p1 == v1.size())break;
            tie(l1, len1) = mat[v1[p1 - 1]][v1[p1]];
            l2 += len;
            len2 -= len;
        } else if (len1 > len2) {
            p2++;
            if (p2 == v2.size())break;
            tie(l2, len2) = mat[v2[p2 - 1]][v2[p2]];
            l1 += len;
            len1 -= len;
        } else {
            p1++, p2++;
            if (p2 == v2.size() || p1 == v1.size())break;
            tie(l1, len1) = mat[v1[p1 - 1]][v1[p1]];
            tie(l2, len2) = mat[v2[p2 - 1]][v2[p2]];
        }
    }
    if (p2 >= v2.size())return 0;
    return 1;
}


vector<int> cnt(N);
vector<vector<array<int, 3>>> adj(N);
vector<vector<int>> ans(N);

void dfs(int node) {
    for (auto[to, _, __]: adj[node]) {
        if (ans[to].empty() || comp(ans[node], ans[to], to)) {
            ans[to] = ans[node];
            ans[to].push_back(to);
        }
        cnt[to]--;
        if (!cnt[to])
            dfs(to);
    }
}

void solve() {
    int st, n, m;
    string s;
    cin >> n >> m >> sz >> st >> s;

    for (int i = 0; i < m; i++) {
        int u, v;
        int l, len;
        cin >> u >> v >> l >> len;
        l--;
        adj[u].push_back({v, l, len});
        mat[u][v] = {l, len};
        cnt[v]++;
    }
    SA(s);

    ans[st] = {st};
    dfs(st);

    for (int i = 1; i <= n; i++) {
        cout << ans[i].size() << ' ';
        for (auto j: ans[i])
            cout << j << ' ';
        cout << '\n';
    }
}

int32_t main() {
    for (int i = 2; i < N; i++) {
        lg[i] = lg[i / 2] + 1;
    }
    std::ios::sync_with_stdio(0), std::cin.tie(0), std::cout.tie(0);
    int t = 1;

//    cin >> t;

    while (t--) {
        solve();
    }

    return 0;
}