#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;

#define fi first
#define se second
#define mp make_pair
#define fastIO ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);

struct Edge{
    int nex;
    int l;
    int r;
};

const int N = 610;
const int MOD = (int)1e9 + 9;
const int B = 77;
const int L = (int)1e6 + 10;
int d;

int id[L];
int pwr[L];
int cum[L];

vector<Edge> E[N];

int get_hash(int l, int r){
    int sum = (cum[r] - cum[l - 1] + MOD) % MOD;
    return (sum * 1ll * pwr[d - r]) % MOD;
}

bool is_equal(int l1, int r1, int l2, int r2){
    return get_hash(l1,r1) == get_hash(l2,r2);
}

int ci = 0;

bool cmp(vector<Edge> A, vector<Edge> B){ // is A < B
    int i = 0, j = 0;
    ci ++ ;
    while(i < A.size() && j < B.size()){
        int len = min(A[i].r - A[i].l, B[j].r - B[j].l) + 1;
        if(len == 0 || is_equal(A[i].l, A[i].l + len - 1, B[j].l, B[j].l + len - 1)){
            A[i].l += len;
            B[j].l += len;
            if(A[i].l > A[i].r) i ++ ;
            if(B[j].l > B[j].r) j ++ ;
        }
        else{
            // find the difference point with binary search and then just compare (;
            int lf = 0, rf = len - 1;
            while(lf < rf){
                int mid = (lf + rf) / 2;
                if(is_equal(A[i].l, A[i].l + mid, B[j].l, B[j].l + mid)){
                    lf = mid + 1;
                }
                else{
                    rf = mid;
                }
            }
            int ii = A[i].l + lf;
            int jj = B[j].l + lf;
            if(id[ii] < id[jj]) return true;
            else return false;
        }
    }
    if(j == B.size()){
        return false;
    }
    else{
        return true;
    }
}

bool vis[N];
bool has[N];
vector<Edge> P[N];

vector<int> ord;
void dfs(int u){
    if(vis[u]) return;
    vis[u]=true;
    for(auto x : E[u]){
        dfs(x.nex);
    }
    ord.push_back(u);
}

int main(){
    fastIO;
    int n, m, s;
    cin >> n >> m >> d >> s;
    int u, v, l, r;
    pwr[0] = 1;
    for(int i = 1; i <= d; i ++ ){
        char f;
        cin >> f;
        id[i] = f - 'a' + 1;
        pwr[i] = (pwr[i - 1] * 1ll * B) % MOD;
        cum[i] = (cum[i - 1] + (pwr[i] * 1ll * id[i]) % MOD) % MOD;
    }
    for(int i = 1; i <= m ; i ++ ){
        cin >> u >> v >> l >> r;
        r = r + l - 1;
        E[u].push_back({v, l, r});
    }
    dfs(s);
    reverse(ord.begin(), ord.end());
    has[s]=true;
    for(auto id : ord){
        if(!has[id]) continue;
        for(auto e : E[id]){
            vector<Edge> X = P[id];
            X.push_back(e);
            if(!has[e.nex] || cmp(X, P[e.nex])){
                P[e.nex] = X;
                has[e.nex]=true;
            }
        }
    }
    for(int it = 1; it <= n; it ++ ){
        if(!has[it]) cout << "0\n";
        else{
            cout << 1 + P[it].size() << " " << s << " ";
            for(auto x : P[it]){
                cout << x.nex << " ";
            }
            cout << "\n";
        }
    }
    return 0;
}