Shortest Palindromic Paths in a Directed Graph

Given a directed graph with \(n\) nodes and \(m\) edges, where each edge is labeled with a letter, and an integer \(d\) followed by a sequence \(s_1, s_2, \dots, s_d\), your task is to determine for every consecutive pair \(s_i\) and \(s_{i+1}\) (for \(1 \le i < d\)) the shortest path from \(s_i\) to \(s_{i+1}\) such that the concatenation of the letters along the path forms a palindrome. If no such path exists, output -1.

Note: A single letter is considered a palindrome, and the path length is determined by the number of edges traversed.

inputFormat

The input begins with a line containing three integers \(n\), \(m\), and \(d\). Each of the following \(m\) lines contains two integers \(u\) and \(v\) and a character, describing a directed edge from node \(u\) to node \(v\) with the given letter. The last line contains \(d\) integers representing the sequence \(s_1, s_2, \dots, s_d\).

outputFormat

For each consecutive pair \(s_i\) and \(s_{i+1}\) (for \(1 \le i < d\)), output a single line containing the palindrome string corresponding to the shortest path. If no palindromic path exists for a pair, output -1.

sample

4 5 3
1 2 a
2 3 b
3 4 a
1 3 x
2 4 y
1 3 4

x
a