#include <iostream>
#include <vector>
#include <queue>
#include <string>
#include <algorithm>
#include <tuple>
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});
    }

    // Output result for each target node
    for (int target = 1; target <= n; target++) {
        vector<string> dp(n + 1, string(d + 1, 'z')); // DP table for shortest string
        vector<int> parent(n + 1, -1); // To reconstruct paths
        dp[s] = ""; // Start at source with empty string

        priority_queue<tuple<string, int>, vector<tuple<string, int>>, greater<>> pq;
        pq.push({"", s});

        while (!pq.empty()) {
            auto [curStr, u] = pq.top();
            pq.pop();

            if (dp[u] < curStr) continue; // Skip if not optimal

            for (auto [edgeStr, v] : adj[u]) {
                string newStr = curStr + edgeStr;

                if (newStr < dp[v] && newStr.size() <= d) {
                    dp[v] = newStr;
                    parent[v] = u; // Update parent for path reconstruction
                    pq.push({newStr, v});
                }
            }
        }

        // Reconstruct path
        if (dp[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;
}