Problem F
Fetch the Stuff

A locked door.

Hannes now wonders if he will be able to fetch all his stuff, and then exit the building. Given a description of the $n$ parts of the university, the $m$ open and locked doors that separate these parts, as well as the $k$ different parts that Hannes needs to visit to fetch his stuff, can you help him determine if he can fetch all his stuff and then exit the building?

Hannes’ current location is in part $1$, and outside the building is represented as part $n$.

Input

The input consists of:

• One line with three integers $n$, $m$ and $k$ ($3 \le n \le 5\, 000$, $1 \le m \le 10^5$, $1 \le k \le 30$), the number of parts of the building, open and locked doors that separate them, and parts that Hannes needs to visit in order to fetch his stuff.

• One line with $k$ distinct integers $p_1,\ldots ,p_ k$ ($1 < p_ i < n$), the parts that Hannes needs to visit in order to fetch his stuff.

• $m$ lines, describing the doors.

  The $i$th such line starts with two integers $q_ i$ and $r_ i$ ($1 \le q_ i, r_ i \le n$, $q_ i \neq r_ i$), indicating that there is a door that separates parts $q_ i$ and $r_ i$ of the building.

  The remainder of the line contains a string $s_ i$, either “open” or “locked”, indicating whether this door is open or locked. If the door is locked, Hannes can only use the door to go from part $q_ i$ of the building to part $r_ i$ of the building. If the door is open, Hannes can use the door to travel between parts $q_ i$ and $r_ i$ as he wishes.

Output

If it is possible for Hannes to pick up all his stuff and then exit the building, output a sequence $t_1,\ldots ,t_ l$ of parts that Hannes can visit, in the order that he should visit them, so that he can pick up all his stuff. It must hold that:

• He starts at his current location, i.e. $t_1 = 1$.

• He ends outside the building, i.e. $t_ l = n$.

• For any two consecutive parts $t_ i$ and $t_{i+1}$ that he visits, there must exist a door that allows Hannes to travel directly from part $t_ i$ of the building to part $t_{i+1}$ of the building.

• Hannes must visit all the parts he needs to visit in order to fetch all his stuff, i.e. for each $i~ \in ~ \{ 1,\ldots ,k\} $ there must exist at least one $j\in \{ 1,\ldots ,l\} $ such that $p_ i = t_ j$.

It is guaranteed that if there exists a valid sequence, there exists a valid sequence of length at most $2\cdot 10^5$. Furthermore, your sequence must satisfy $l \le 2\cdot 10^5$. If there are multiple valid sequences, you may output any of them.

If it is not possible for Hannes to pick up all his stuff and then exit the building, output “impossible”.

4 4 2
2 3
1 3 locked
3 4 locked
1 2 locked
2 4 open

1
3
4
2
4

5 7 2
3 4
1 2 locked
1 3 open
2 3 locked
1 5 locked
2 4 locked
5 4 locked
5 4 open

1
3
1
5
4
5

5 5 2
2 4
1 2 locked
1 3 locked
2 3 locked
1 5 locked
5 4 open

impossible