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

int main() {
    int n, m, d, s;
    cin >> n >> m >> d >> s;

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

    vector<vector<pair<string, int>>> adj(n + 1); // {substring, target node}
    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});
    }

    // Process each target node
    for (int target = 1; target <= n; target++) {
        queue<pair<int, string>> bfsQueue; // {current node, accumulated string}
        vector<int> parent(n + 1, -1);    // Parent for path reconstruction
        vector<string> best(n + 1, string(d + 1, 'z')); // Best string to reach each node
        vector<bool> visited(n + 1, false);

        bfsQueue.push({s, ""});
        best[s] = "";
        visited[s] = true;

        while (!bfsQueue.empty()) {
            auto [node, curString] = bfsQueue.front();
            bfsQueue.pop();

            if (node == target) continue; // Skip further processing for the target

            for (auto [edge, neighbor] : adj[node]) {
                string newString = curString + edge;

                // Check if the new path is better
                if (newString < best[neighbor] && newString.size() <= d) {
                    best[neighbor] = newString;
                    parent[neighbor] = node;
                    bfsQueue.push({neighbor, newString});
                }
            }
        }

        // Output result for target
        if (best[target] == string(d + 1, 'z')) {
            cout << 0 << "\n"; // No path found
        } else {
            vector<int> path;
            for (int v = target; v != -1; v = parent[v]) {
                path.push_back(v);
            }
            reverse(path.begin(), path.end());

            cout << path.size() << " ";
            for (int node : path) {
                cout << node << " ";
            }
            cout << "\n";
        }
    }

    return 0;
}