#include <iostream>
#include <vector>
#include <queue>
#include <string>
#include <limits>
#include <algorithm>

using namespace std;

const int INF = numeric_limits<int>::max();

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m, d, s;
    cin >> n >> m >> d >> s;

    string A;
    cin >> A;

    vector<vector<pair<string, int>>> adj(n+1);
    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 target = 1; target <= n; target++) {
        vector<int> dist(n+1, INF);
        vector<int> prev(n+1, -1);
        dist[s] = 0;

        queue<pair<int, string>> q;
        q.push({s, ""});

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

            if (node == target) break;

            for (auto [edgeLabel, nextNode] : adj[node]) {
                if (dist[nextNode] > dist[node] + 1) {
                    dist[nextNode] = dist[node] + 1;
                    prev[nextNode] = node;
                    q.push({nextNode, currentPath + edgeLabel});
                }
            }
        }

        if (dist[target] == INF) {
            cout << 0 << "\n";
        } else {
            vector<int> path;
            for (int at = target; at != -1; at = prev[at]) {
                path.push_back(at);
            }
            reverse(path.begin(), path.end());

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

    return 0;
}