The Walk of Bytie-boy

Bytie-boy is one of the youngest residents of Byteburg. He has only just learned to read and write, but he is old enough to walk to school on his own. Every morning he leaves home and calls on each of his friends in turn; the whole group sets off to school together only once everyone has joined.

One day the teacher asked Bytie to prepare a list of the streets he walks on his way to school and to read it aloud in the next class. To keep the list short, Bytie decided to write down only the first letter of the name of each street he uses. All streets in Byteburg are one-way, and each one connects two different crossings.

Bytie pauses only at the crossings where he picks up a friend, so each part of his walk (between two consecutive stops) reads as a single word. Reading is still hard for him, and he sometimes reads a word right to left instead of left to right, so he might read milk as either milk or klim. To spare him mistakes, his parents want a route in which every such word is a palindrome: it reads the same left to right and right to left. They also want each word to be as short as possible.

You are given the city and the ordered list of crossings where Bytie stops. For each consecutive pair of stops, find the shortest walk along the one-way streets whose sequence of first letters forms a palindrome.

The first line contains two integers $n$ and $m$ ($2 \le n \le 400$, $1 \le m \le 60000$): the number of crossings in Byteburg and the number of one-way streets.

Each of the next $m$ lines contains two integers and a letter, $x_i$ $y_i$ $c_i$ ($1 \le x_i \le n$, $1 \le y_i \le n$, $x_i \ne y_i$), describing a one-way street that leads from crossing $x_i$ to crossing $y_i$ and whose name starts with the lowercase English letter $c_i$. For any ordered pair of crossings there is at most one street, so there is at most one street from $x$ to $y$ and at most one from $y$ to $x$.

The next line contains one integer $d$ ($2 \le d \le 100$): the number of crossings on Bytie's route.

The last line contains $d$ integers $s_1, s_2, \ldots, s_d$ ($1 \le s_i \le n$): the crossings in the order Bytie visits them, where $s_1$ is his home and $s_d$ is the school. Every two consecutive values differ, but values that are not adjacent may be equal.

Print $d - 1$ lines. On the $i$-th line describe the shortest palindromic walk from crossing $s_i$ to crossing $s_{i+1}$ along the one-way streets: print its length $r_i$ (the number of streets used) and then, separated by a single space, the string $w_i$ of first letters read along that walk. A walk is palindromic when $w_i$ reads the same left to right and right to left; a walk of a single street counts as palindromic. If several shortest palindromic walks exist, print the one whose letter string $w_i$ is lexicographically smallest. If no palindromic walk from $s_i$ to $s_{i+1}$ exists, print -1 on that line instead.