라벨이 붙은 경로

방향 비순환 그래프(DAG)가 주어진다. 정점은 $n$개, 간선은 $m$개이다. 각 간선에는 소문자로 이루어진 라벨이 붙어 있으며, 빈 문자열일 수도 있다. 경로의 라벨은 경로 순서대로 간선의 라벨을 이어 붙인 문자열이다. 시작 정점 $s$에서 도착 정점 $t$까지 가는 경로 중 라벨이 사전순으로 가장 작은 경로를 최소 경로라고 한다. 주어진 $s$에 대해, 모든 정점 $t$까지의 최소 경로를 구하라.

첫 줄에 정수 $n$, $m$, $d$, $s$가 공백으로 구분되어 주어진다. $d$는 아래에 나오는 문자열 $A$의 길이이다. 정점은 1부터 $n$까지 번호가 매겨져 있다.

둘째 줄에는 길이가 정확히 $d$인 문자열 $A$가 주어진다. 모든 문자는 영어 소문자이다. 간선의 라벨은 모두 $A$의 부분 문자열이다.

이어지는 $m$개의 줄 중 $i$번째 줄에는 정수 $u_i$, $v_i$, $p_i$, $\ell_i$가 주어진다. $i$번째 간선은 $u_i$에서 $v_i$로 향하며, 라벨은 $A$의 $p_i$번째 문자부터 시작하는 길이 $\ell_i$인 부분 문자열이다. $A$의 문자는 1부터 $d$까지 번호가 매겨져 있다.

$n$개의 줄을 출력한다. $t$번째 줄에는 $s$에서 $t$까지의 최소 경로를 출력한다. $s$에서 $t$로 가는 경로가 없으면 정수 0만 출력한다. 그렇지 않으면 경로의 정점 개수($s$와 $t$ 포함)를 먼저 쓰고, 경로 순서대로 정점 번호를 공백으로 구분해 출력한다. 해가 여러 개이면 그중 아무거나 출력해도 된다.

• $1 \le s \le n \le 600$
• $1 \le m \le 2000$
• $1 \le d \le 10^6$
• $1 \le u_i \le n$, $1 \le v_i \le n$, 모든 $i$에 대해 $u_i \ne v_i$
• $1 \le p_i$, $0 \le \ell_i$, 모든 $i$에 대해 $p_i + \ell_i - 1 \le d$
• 그래프는 비순환이며 평행 간선이 없다. 즉, $i \ne j$이면 $u_i \ne u_j$ 또는 $v_i \ne v_j$이다.

이 예제에서 간선 $3 \to 1$의 라벨은 ab이고, 간선 $1 \to 4$의 라벨은 a이다. 3에서 4까지의 최소 경로는 $3 \to 1 \to 4$이며, 그 라벨은 aba이다.