给定一个包含 $n$ 个顶点和 $m$ 条边的有向无环图。每条边都有一个标签（一个由小写字母组成的字符串，也可能是空串）。我们可以将标签的概念从边扩展到路径，定义路径的标签为构成该路径的所有边的标签按出现顺序连接而成的字符串。从起点 $s$ 到终点 $t$ 的“最小路径”是指在所有从 $s$ 到 $t$ 的路径中，其标签在字典序中最小（即字典序最靠前）的那条路径。请编写一个程序，对于给定的起点 $s$，输出图中所有顶点 $t$ 的最小路径。

输入格式

第一行包含四个由空格分隔的整数：$n$（顶点数）、$m$（边数）、$d$（字符串 $A$ 的长度，详见下文）和 $s$（起点编号）。顶点编号为 $1$ 到 $n$。

第二行包含一个长度恰好为 $d$ 的字符串 $A$；该字符串的所有字符均为英文小写字母。图中所有边的标签均为字符串 $A$ 的子串。

接下来的 $m$ 行描述图中的边。第 $i$ 行描述第 $i$ 条边，包含四个由空格分隔的整数：$u_i$（边的起点）、$v_i$（边的终点）、$p_i$ 和 $\ell_i$。后两个整数表示该边的标签是字符串 $A$ 中从第 $p_i$ 个字符开始、长度为 $\ell_i$ 的子串。在此处，我们认为 $A$ 的字符索引从 $1$ 到 $d$。

数据范围

• $1 \le s \le n \le 600$
• $1 \le m \le 2\,000$
• $1 \le d \le 10^6$
• $1 \le u_i \le n, 1 \le v_i \le n, u_i \neq v_i$（对于所有 $i = 1, \dots, m$）
• $1 \le p_i, 0 \le \ell_i, p_i + \ell_i - 1 \le d$（对于所有 $i = 1, \dots, m$）
• 该图为有向无环图，且没有平行边（即对于 $i \neq j$，满足 $u_i \neq u_j$ 或 $v_i \neq v_j$）。

输出格式

输出 $n$ 行，其中第 $t$ 行（对于 $t = 1, \dots, n$）描述从 $s$ 到 $t$ 的最小路径。如果不存在从 $s$ 到 $t$ 的路径，该行应仅包含整数 $0$。否则，该行应以路径上的顶点数量（包含起点 $s$ 和终点 $t$）开头，随后依次列出路径上的顶点，并用空格分隔。如果存在多种可能的解，输出其中任意一个即可。

样例

输入 1

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

输出 1

2 3 1
2 3 2
1 3
3 3 1 4
3 3 2 5

说明

在此样例中，边 $3 \to 1$ 的标签为 ab；边 $1 \to 4$ 的标签为 a；从 $3$ 到 $4$ 的最小路径为 $3 \to 1 \to 4$，其标签为 aba。