We are given a directed acyclic graph with $$$n$$$ vertices and $$$m$$$ edges. Each edge has a label (a string of lowercase letters; possibly even an empty string). We can now extend the concept of labels from edges to paths by defining the label of a path as the concatenation of the labels of the edges that constitute this path (in the same order in which they appear in the path). The smallest path from a start vertex $$$s$$$ to a destination vertex $$$t$$$ is the path (from $$$s$$$ to $$$t$$$) whose label is lexicographically smallest (i.e. the earliest in lexicographical order) amongst all the paths from $$$s$$$ to $$$t$$$. Write a program that, for a given $$$s$$$, outputs the smallest paths from $$$s$$$ to $$$t$$$ for all vertices $$$t$$$ of the graph.
The first line contains four space-separated integers: $$$n$$$ (the number of vertices), $$$m$$$ (the number of edges), $$$d$$$ (the length of the string $$$A$$$, on which see below) and $$$s$$$ (the number of the start vertex). The vertices are numbered by integers from $$$1$$$ to $$$n$$$.
The second line contains a string $$$A$$$, which is exactly $$$d$$$ characters long; all these characters are lowercase letters of the English alphabet. All the edge labels in our graph are substrings of the string $$$A$$$.
The remaining $$$m$$$ lines describe the edges of the graph. The $$$i$$$-th of these lines describes the $$$i$$$-th edge and contains four space-separated integers: $$$u_i$$$ (the start vertex of this edge), $$$v_i$$$ (the end vertex of this edge), $$$p_i$$$ and $$$\ell_i$$$. The last two of these integers indicate that the label of this edge is the substring of $$$A$$$ that begins with the $$$p_i$$$-th character of $$$A$$$ and is $$$\ell_i$$$ characters long. For this purpose we consider the characters of $$$A$$$ to be indexed by integers from $$$1$$$ to $$$d$$$.
Input limits
Output $$$n$$$ lines, where the $$$t$$$-th line (for $$$t = 1, \ldots , n$$$) describes the smallest path from $$$s$$$ to $$$t$$$. If there is no path from $$$s$$$ to $$$t$$$, the line should contain only the integer $$$0$$$ and nothing else. Otherwise the line should start with the number of vertices on the path (including vertices $$$s$$$ and $$$t$$$), followed by the list of those vertices, separated by spaces. If there are several possible solutions, you may output any of them.
5 7 6 3 abcbca 3 2 1 1 2 1 5 1 2 5 4 2 3 1 1 2 3 4 3 2 1 4 6 1 5 4 5 2
2 3 1 2 3 2 1 3 3 3 1 4 3 3 2 5
In this example, the edge $$$3 \to 1$$$ has the label $$$\texttt{ab}$$$; the edge $$$1 \to 4$$$ has the label $$$\texttt{a}$$$; the smallest path from $$$3$$$ to $$$4$$$ is $$$3 \to 1 \to 4$$$, whose label is $$$\texttt{aba}$$$.
