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

class SuffixArray {
private:
    vector<int> sa, rank, lcp;
    vector<int> tempSA, tempRank;
    
    void countingSort(int k, int n) {
        vector<int> count(max(300, n) + 1, 0);
        
        // Count occurrences
        for (int i = 0; i < n; i++) 
            count[rank[min(n-1, sa[i] + k)]]++;
        
        // Calculate cumulative count
        for (int i = 1; i <= max(300, n); i++)
            count[i] += count[i-1];
        
        // Build temporary SA
        for (int i = n - 1; i >= 0; i--) {
            int r = min(n-1, sa[i] + k);
            tempSA[--count[rank[r]]] = sa[i];
        }
        
        // Copy back
        sa = tempSA;
    }
    
    void buildSA(vector<int>& a) {
        int n = a.size();
        sa.resize(n);
        rank.resize(n);
        tempSA.resize(n);
        tempRank.resize(n);
        
        // Initial rank is the character value
        for (int i = 0; i < n; i++) {
            sa[i] = i;
            rank[i] = a[i];
        }
        
        // Sort with increasing k
        for (int k = 1; k < n; k *= 2) {
            countingSort(k, n);
            countingSort(0, n);
            
            // Assign new ranks
            tempRank[sa[0]] = 0;
            for (int i = 1; i < n; i++) {
                int prev = sa[i-1], curr = sa[i];
                tempRank[curr] = tempRank[prev] + 
                    (rank[prev] != rank[curr] || 
                     rank[min(n-1, prev+k)] != rank[min(n-1, curr+k)]);
            }
            
            rank = tempRank;
            if (rank[sa[n-1]] == n-1) break;
        }
    }
    
public:
    void init(vector<int>& a) {
        buildSA(a);
    }
    
    int getLCP(int x, int y, const vector<int>& a) {
        int n = a.size();
        int lcp = 0;
        while (x + lcp < n && y + lcp < n && a[x + lcp] == a[y + lcp]) 
            lcp++;
        return lcp;
    }
};

bool comparePaths(const vector<pair<string, vector<int>>>& path1, 
                  const vector<pair<string, vector<int>>>& path2, 
                  const string& A) {
    if (path1.empty()) return false;
    if (path2.empty()) return true;
    
    vector<int> p1 = path1.back().second;
    vector<int> p2 = path2.back().second;
    
    reverse(p1.begin(), p1.end());
    reverse(p2.begin(), p2.end());
    
    int i = 0, j = 0;
    while (i < p1.size() && j < p2.size()) {
        int lcp = 0;
        // Compare substrings 
        while (i+lcp < p1.size() && j+lcp < p2.size()) {
            if (A[p1[i+lcp]] != A[p2[j+lcp]]) break;
            lcp++;
        }
        
        // If different after common prefix, compare lexicographically
        if (i+lcp < p1.size() && j+lcp < p2.size()) {
            return A[p1[i+lcp]] < A[p2[j+lcp]];
        }
        
        // If one path is a prefix of another, shorter path is less
        if (i+lcp == p1.size()) return true;
        if (j+lcp == p2.size()) return false;
        
        i += lcp;
        j += lcp;
    }
    
    return p1.size() < p2.size();
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    
    int n, m, d, s;
    cin >> n >> m >> d >> s;

    string A;  // All edge labels are substrings of A
    cin >> A;

    vector<pair<string, int>> adj[n+1]; //target, substring
    for (int i = 0; i < m; i++) {
        int u, v, p, l;
        cin >> u >> v >> p >> l;
        adj[u].push_back({A.substr(p-1, l), v});
    }

    for (int i = 1; i <= n; i++) {
        vector<vector<pair<string, vector<int>>>> bestPaths(n+1);
        bestPaths[s].push_back({"", {s}});

        for (int depth = 0; depth < n; depth++) {
            vector<vector<pair<string, vector<int>>>> newPaths(n+1);
            
            for (int u = 1; u <= n; u++) {
                for (auto& path : bestPaths[u]) {
                    int currNode = path.second.back();
                    
                    // If target reached, update best paths
                    if (currNode == i) {
                        if (newPaths[u].empty() || 
                            comparePaths({path}, newPaths[u], A)) {
                            newPaths[u] = {path};
                        }
                        continue;
                    }
                    
                    // Explore adjacent nodes
                    for (auto& [edgeLabel, nextNode] : adj[currNode]) {
                        auto newPath = path;
                        newPath.first += edgeLabel;
                        newPath.second.push_back(nextNode);
                        
                        // Update if new path is better
                        if (newPaths[nextNode].empty() || 
                            comparePaths({newPath}, newPaths[nextNode], A)) {
                            newPaths[nextNode] = {newPath};
                        }
                    }
                }
            }
            
            // Replace paths
            bestPaths = newPaths;
        }

        // Output result for current destination
        if (bestPaths[i].empty()) {
            cout << 0 << "\n";
        } else {
            auto& bestPath = bestPaths[i][0];
            cout << bestPath.second.size() << " ";
            for (int node : bestPath.second) 
                cout << node << " ";
            cout << "\n";
        }
    }
    
    return 0;
}