#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

typedef vector<int> VI;

struct Edge {
    int u, v, l, p;
};

vector<Edge> edges;
VI a;

struct SuffixArray {
    vector<int> sa, rank, lcp;

    void init(const VI &str) {
        int n = str.size();
        sa.resize(n);
        rank.resize(n);
        lcp.resize(n);
        iota(sa.begin(), sa.end(), 0);
        sort(sa.begin(), sa.end(), [&str](int i, int j) { return str[i] < str[j]; });
        
        for (int i = 0; i < n; i++) rank[sa[i]] = i;

        for (int len = 1; len < n; len *= 2) {
            sort(sa.begin(), sa.end(), [&](int i, int j) {
                if (rank[i] != rank[j]) return rank[i] < rank[j];
                int ri = i + len < n ? rank[i + len] : -1;
                int rj = j + len < n ? rank[j + len] : -1;
                return ri < rj;
            });

            vector<int> new_rank(n);
            new_rank[sa[0]] = 0;
            for (int i = 1; i < n; i++) {
                new_rank[sa[i]] = new_rank[sa[i - 1]];
                if (rank[sa[i]] != rank[sa[i - 1]] || (sa[i] + len < n && sa[i - 1] + len < n && rank[sa[i] + len] != rank[sa[i - 1] + len]))
                    new_rank[sa[i]]++;
            }
            rank = new_rank;
        }

        // Calculate LCP array
        for (int i = 0, h = 0; i < n; i++) {
            if (rank[i] > 0) {
                int j = sa[rank[i] - 1];
                while (i + h < n && j + h < n && str[i + h] == str[j + h]) h++;
                lcp[rank[i] - 1] = h;
                if (h > 0) h--;
            }
        }
    }

    int queryLcp(int i, int j) {
        return (i < lcp.size()) ? lcp[i] : 0;
    }
};

struct Lcp {
    SuffixArray sa;

    void init(SuffixArray &suffixArray) {
        sa = suffixArray;
    }
};

bool cmp(VI path1, VI path2, const Lcp &lcp) {
    if (path1.empty()) return false;
    if (path2.empty()) return true;

    reverse(path1.begin(), path1.end());
    reverse(path2.begin(), path2.end());
    int i[2] = {0, 0};
    int j[2] = {0, 0};
    while (i[0] < path1.size() && i[1] < path2.size()) {
        const Edge& edge1 = edges[path1[i[0]]];
        const Edge& edge2 = edges[path2[i[1]]];
        int x = lcp.sa.queryLcp(edge1.l + j[0], edge2.l + j[1]);
        int y[2] = {edge1.p - j[0], edge2.p - j[1]};

        if (x < y[0] && x < y[1]) {
            return a[edge1.l + j[0] + x] < a[edge2.l + j[1] + x];
        }

        x = min(x, min(y[0], y[1]));
        for (int t = 0; t < 2; t++) {
            if (x == y[t]) {
                i[t]++;
                j[t] = 0;
            } else {
                j[t] += x;
            }
        }
    }
    return i[0] == path1.size() && i[1] < path2.size();
}

void dfs(int v, const vector<VI> &g, vector<int> &usedInDfs, VI &order) {
    usedInDfs[v] = 1;
    for (int i : g[v]) {
        int to = edges[i].v;
        if (!usedInDfs[to]) dfs(to, g, usedInDfs, order);
    }
    order.push_back(v);
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    int n, m, d, s;
    cin >> n >> m >> d >> s;
    s--;

    string str;
    cin >> str;
    a.resize(d);
    for (int i = 0; i < d; i++) {
        a[i] = str[i] - 'a';
    }

    edges.resize(m);
    vector<VI> g(n), gr(n);
    for (int i = 0; i < m; i++) {
        Edge &edge = edges[i];
        cin >> edge.u >> edge.v >> edge.l >> edge.p;
        edge.u--;
        edge.v--;
        edge.l--;
        g[edge.u].push_back(i);
        gr[edge.v].push_back(i);
    }

    SuffixArray sa;
    sa.init(a);
    Lcp lcp;
    lcp.init(sa);

    vector<int> usedInDfs(n, 0), order;
    dfs(s, g, usedInDfs, order);

    for (int u = 0; u < n; u++) {
        vector<VI> bestPath(n);
        for (int v : order) {
            if (u != v && bestPath[v].empty()) continue;
            VI path = bestPath[v];
            for (int i : gr[v]) {
                int to = edges[i].u;
                path.push_back(i);
                if (cmp(path, bestPath[to], lcp)) bestPath[to] = path;
                path.pop_back();
            }
        }

        if (u != s && bestPath[s].empty()) {
            cout << "0\n";
        } else {
            reverse(bestPath[s].begin(), bestPath[s].end());
            cout << bestPath[s].size() + 1 << " " << s + 1;
            for (int i : bestPath[s]) cout << " " << edges[i].v + 1;
            cout << "\n";
        }
    }

    return 0;
}

answer.code: In member function ‘void SuffixArray::init(const VI&)’:
answer.code:23:9: error: ‘iota’ was not declared in this scope
   23 |         iota(sa.begin(), sa.end(), 0);
      |         ^~~~
answer.code: In function ‘bool cmp(VI, VI, const Lcp&)’:
answer.code:81:32: error: passing ‘const SuffixArray’ as ‘this’ argument discards qualifiers [-fpermissive]
   81 |         int x = lcp.sa.queryLcp(edge1.l + j[0], edge2.l + j[1]);
      |                 ~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
answer.code:57:9: note:   in call to ‘int SuffixArray::queryLcp(int, int)’
   57 |     int queryLcp(int i, int j) {
      |         ^~~~~~~~