D. String Automaton
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Recently, you found an interesting machine that turned out to be a string automaton. This device defines a certain set of valid strings and, for a specific string, indicates whether that string belongs to its alphabet.

After some time, you figured out the structure of the automaton – it has $$$n$$$ vertices and $$$m$$$ directed edges between them. Each edge is labeled with a letter from the Latin alphabet, and some vertices are terminal. The graph may contain loops and multiple edges.

The automaton considers a string of Latin characters to be $$$valid$$$ if the following process can end in a terminal vertex.

Initially, $$$x = 1$$$ – the current state. Then, the characters of the string are considered one by one. If there is no transition from the current vertex for the next character $$$s$$$, the process ends, and the string is considered invalid. If there are transitions for the character $$$s$$$, the state changes to one of the states reachable from $$$x$$$ by the letter $$$s$$$.

Note that there may be multiple transitions from one vertex for the letter $$$s$$$, but for the string to be considered valid, it is sufficient that at least one path ends in a terminal vertex.

Additionally, the empty string is considered $$$valid$$$ regardless of the structure of the automaton.

You need to determine the maximum length of a string that is $$$valid$$$.

If the length is finite, you should output the lexicographically smallest string of maximum length.

For strings of the same length $$$S, T$$$ $$$(S \ne T)$$$, $$$S$$$ is called lexicographically smaller than $$$T$$$ if there exists an $$$i$$$ such that for $$$j$$$ ($$$1 \le j \lt i$$$) $$$S_{j} = T_j$$$ and $$$S_{i} \lt T_i$$$.

Input

The first line contains the numbers $$$n, m$$$, and $$$k$$$ ($$$1 \le n, m, k \le 5 \cdot 10^5$$$) – the number of vertices, edges in the automaton, and the number of terminal vertices.

The next $$$m$$$ lines contain 3 numbers $$$u, v, s$$$, indicating that there is a directed edge from $$$u$$$ to $$$v$$$ with the letter $$$s$$$ $$$(1 \le u,v \le n)$$$, where $$$s$$$ is a character from the Latin alphabet.

The following line contains $$$k$$$ numbers $$$u_1, u_2, \ldots, u_k\, (1\le u_i \le n)$$$ – the terminal vertices.

Output

In the first line, output «inf» if there exist infinitely long $$$valid$$$ strings.

Otherwise, output the length of the longest $$$valid$$$ string, and in the next line, output the lexicographically smallest string that is $$$valid$$$.

Examples
Input
4 4 2
1 2 a
2 3 b
1 3 b
4 4 a
3 4
Output
2
ab
Input
3 4 1
1 2 a
1 3 c
3 2 c
2 2 a
3
Output
1
c