VI a;
SuffixArray sa;
Lcp lcp;

struct Edge
{
	int u, v, l, p;
};

vector<Edge> edges;

bool cmp(const VI& path1, const VI& path2)
{
	if (path1.empty())
		return false;
	if (path2.empty())
		return true;
	int i[2] = {0, 0};
	int j[2] = {0, 0};
	while (i[0] < SZ(path1) && i[1] < SZ(path2))
	{
		const Edge& edge1 = edges[path1[i[0]]];
		const Edge& edge2 = edges[path2[i[1]]];
		int x = lcp.queryLcp(edge1.l + j[0], edge2.l + j[1]);
		int y[2] = {edge1.p - j[0], edge2.p - j[1]};
		if (x < y[0] && x < y[1])
		{
			return a[edge1.l + j[0] + x] < a[edge2.l + j[1] + x];
		}
		x = min(x, min(y[0], y[1]));
		FOR(t, 0, 2)
		{
			if (x == y[t])
			{
				i[t]++;
				j[t] = 0;
			}
			else
			{
				j[t] += x;
			}
		}
	}
	return i[0] == SZ(path1) && i[1] < SZ(path2);
}

int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	int n, m, d, s;
	cin >> n >> m >> d >> s;
	s--;
	string str;
	cin >> str;
	edges.resize(m);
	vector<VI> g(n);
	FOR(i, 0, m)
	{
		Edge& edge = edges[i];
		cin >> edge.u >> edge.v >> edge.l >> edge.p;
		edge.u--;
		edge.v--;
		edge.l--;
		g[edge.u].PB(i);
	}
	a.resize(d);
	FOR(i, 0, d)
	{
		a[i] = str[i] - 'a';
	}
	sa.init(a);
	lcp.init(sa);
	VI used(n);
	vector<VI> bestPath(n);
	FOR(k, 0, n)
	{
		int v = k == 0 ? s : -1;
		if (k > 0)
		{
			FOR(j, 0, n)
			{
				if (!used[j] && (v == -1 || cmp(bestPath[j], bestPath[v])))
				{
					v = j;
				}
			}
		}
		used[v] = 1;
		VI path = bestPath[v];
		for (int i : g[v])
		{
			int to = edges[i].v;
			path.PB(i);
			if (cmp(path, bestPath[to]))
			{
				bestPath[to] = path;
			}
			path.pop_back();
		}
	}
	FOR(v, 0, n)
	{
		cout << SZ(bestPath[v]) + 1 << " " << s + 1;
		for (int i : bestPath[v])
			cout << " " << edges[i].v + 1;
		cout << "\n";
	}
	return 0;
}

answer.code:1:1: error: ‘VI’ does not name a type
    1 | VI a;
      | ^~
answer.code:2:1: error: ‘SuffixArray’ does not name a type
    2 | SuffixArray sa;
      | ^~~~~~~~~~~
answer.code:3:1: error: ‘Lcp’ does not name a type
    3 | Lcp lcp;
      | ^~~
answer.code:10:1: error: ‘vector’ does not name a type
   10 | vector<Edge> edges;
      | ^~~~~~
answer.code:12:16: error: ‘VI’ does not name a type
   12 | bool cmp(const VI& path1, const VI& path2)
      |                ^~
answer.code:12:33: error: ‘VI’ does not name a type
   12 | bool cmp(const VI& path1, const VI& path2)
      |                                 ^~
answer.code: In function ‘bool cmp(const int&, const int&)’:
answer.code:14:19: error: request for member ‘empty’ in ‘path1’, which is of non-class type ‘const int’
   14 |         if (path1.empty())
      |                   ^~~~~
answer.code:16:19: error: request for member ‘empty’ in ‘path2’, which is of non-class type ‘const int’
   16 |         if (path2.empty())
      |                   ^~~~~
answer.code:20:23: error: ‘SZ’ was not declared in this scope
   20 |         while (i[0] < SZ(path1) && i[1] < SZ(path2))
      |                       ^~
answer.code:22:37: error: ‘edges’ was not declared in this scope; did you mean ‘edge1’?
   22 |                 const Edge& edge1 = edges[path1[i[0]]];
      |                                     ^~~~~
      |                                     edge1
answer.code:22:48: error: invalid types ‘const int[int]’ for array subscript
   22 |                 const Edge& edge1 = edges[path1[i[0]]];
      |                                                ^
answer.code:23:48: error: invalid types ‘const int[int]’ for array subscript
   23 |                 const Edge& edge2 = edges[path2[i[1]]];
      |                                                ^
answer.code:24:25: error: ‘lcp’ was not declared in this scope
   24 |                 int x = lcp.queryLcp(edge1.l + j[0], edge2.l + j[1]);
      |                         ^~~
answer.code:28:32: error: ‘a’ was not declared in this scope
   28 |                         return a[edge1.l + j[0] + x] < a[edge2.l + j[1] + x];
      |                                ^
answer.code:30:28: error: ‘min’ was not declared in this scope
   30 |                 x = min(x, min(y[0], y[1]));
      |                            ^~~
answer.code:30:21: error: ‘min’ was not declared in this scope
   30 |                 x = min(x, min(y[0], y[1]));
      |                     ^~~
answer.code:31:21: error: ‘t’ was not declared in this scope
   31 |                 FOR(t, 0, 2)
      |                     ^
answer.code:31:17: error: ‘FOR’ was not declared in this scope
   31 |                 FOR(t, 0, 2)
      |                 ^~~
answer.code:44:24: error: ‘SZ’ was not declared in this scope
   44 |         return i[0] == SZ(path1) && i[1] < SZ(path2);
      |                        ^~
answer.code: In function ‘int main()’:
answer.code:49:9: error: ‘ios’ has not been declared
   49 |         ios::sync_with_stdio(0);
      |         ^~~
answer.code:50:9: error: ‘cin’ was not declared in this scope
   50 |         cin.tie(0);
      |         ^~~
answer.code:54:9: error: ‘string’ was not declared in this scope
   54 |         string str;
      |         ^~~~~~
answer.code:55:16: error: ‘str’ was not declared in this scope; did you mean ‘std’?
   55 |         cin >> str;
      |                ^~~
      |                std
answer.code:56:9: error: ‘edges’ was not declared in this scope
   56 |         edges.resize(m);
      |         ^~~~~
answer.code:57:16: error: ‘VI’ was not declared in this scope
   57 |         vector<VI> g(n);
      |                ^~
answer.code:57:9: error: ‘vector’ was not declared in this scope
   57 |         vector<VI> g(n);
      |         ^~~~~~
answer.code:57:20: error: ‘g’ was not declared in this scope
   57 |         vector<VI> g(n);
      |                    ^
answer.code:58:13: error: ‘i’ was not declared in this scope
   58 |         FOR(i, 0, m)
      |             ^
answer.code:58:9: error: ‘FOR’ was not declared in this scope
   58 |         FOR(i, 0, m)
      |         ^~~
answer.code:67:9: error: ‘a’ was not declared in this scope
   67 |         a.resize(d);
      |         ^
answer.code:72:9: error: ‘sa’ was not declared in this scope; did you mean ‘s’?
   72 |         sa.init(a);
      |         ^~
      |         s
answer.code:73:9: error: ‘lcp’ was not declared in this scope
   73 |         lcp.init(sa);
      |         ^~~
answer.code:74:11: error: expected ‘;’ before ‘used’
   74 |         VI used(n);
      |           ^~~~~
      |           ;
answer.code:75:20: error: ‘bestPath’ was not declared in this scope
   75 |         vector<VI> bestPath(n);
      |                    ^~~~~~~~
answer.code:76:13: error: ‘k’ was not declared in this scope
   76 |         FOR(k, 0, n)
      |             ^
answer.code:102:13: error: ‘v’ was not declared in this scope
  102 |         FOR(v...