Description

You are given a directed graph with $n$ vertices and $m$ edges. Each edge has a letter on it. You are also given an integer $d$ and a sequence $s_1, s_2, \dots, s_d$.

For each $i$ ($1 \le i < d$), you need to find a shortest path from $s_i$ to $s_{i+1}$ such that the letters on the edges of this path, concatenated in order, form a palindrome.

It is not guaranteed that each vertex appears at most once in $s$.

Input Format

The first line contains two integers $n, m$.

Then follow $m$ lines. Each line contains two integers $x_i, y_i$ and a letter $c_i$, indicating there is a directed edge from $x_i$ to $y_i$, and the letter on this edge is $c_i$.

The next line contains an integer $d$.

The last line contains $d$ integers, giving the sequence $s$.

Output Format

Output $d-1$ lines. On the $i$-th line, output a path from $s_i$ to $s_{i+1}$ that satisfies the condition.

If no such path exists, output -1; otherwise, output all letters on this path.

If there are multiple valid paths, output any one of them.

6 7
1 2 a
1 3 x
1 4 b
2 6 l
3 5 y
4 5 z
6 5 a
3
1 5 3

3 ala
-1

Hint

For $100\%$ of the testdata, $2 \le n \le 400$, $1 \le m \le 6\times 10^4$, $1 \le x_i, y_i \le n$, $2 \le d \le 100$, $1 \le s_i \le n$.

It is also guaranteed that there are no multiple edges or self-loops.

Translated by ChatGPT 5