package main

import "fmt"

type Triplet struct {
    first int
    second int
    third string
}

type Pair struct {
    one []int
    two string
}

func PrintMe(mas []Triplet, n int, m int, final []int) {
    for i:=0; i<m; i++ {
        fmt.Print(mas[i].first, " ")
        fmt.Print(mas[i].second, " ")
        fmt.Println(mas[i].third)
    }
    for i:=0; i<n; i++ {
        fmt.Print(final[i], " ")
    }
    fmt.Println()
}

func NewSet(n int) ([]int) {
    c := make([]int, n)
    for i:=0; i<n; i++ {
        c[i] = -1
    }
    return c
}

func Closure(mas []Triplet, z []int) ([]int) {
    C := NewSet(len(mas))
    //fmt.Println("z = ", z)
    for q:=0; q<len(z); q++ {
        if z[q] != -1 {
            DFS(mas, z[q], C)
        }
    }
    return C
}

func DFS(mas []Triplet, q int, C []int) {
    //fmt.Println("q = ", q)
    //fmt.Println("CB = ", C)
    if !Search(C, q) {  //если q не принадлежит С
        for i:=0; i<len(C); i++ {
            if C[i] == -1 { //если первый элемент С пустой,
                C[i] = q    //кидаю туда q
                break
            }
        }
        //fmt.Println("CD = ", C)
        for i:=0; i<len(mas); i++ {
            if mas[i].first == q && mas[i].third == "lambda" {
                DFS(mas, mas[i].second, C)
            }
        }
    }
}

func Search(Qn []int, qn int) (bool) {
    var eq bool
    for i:= range Qn {
        if Qn[i] == qn {
            eq = true
            break
        }
    }
    return eq
}

func newStack(n int) ([][]int)  {
    stack := make([][]int, n, n)
    for i:=0; i<n; i++ {
        stack[i] = make([]int, n)
    }
    for i:=0; i<n; i++ {
        for j:=0; j<n; j++ {
            stack[i][j] = -1
        }
    }
    return stack
}

func Pop(stack [][]int) ([]int) {
    for i:=len(stack)-1; i>=0; i-- {
        //fmt.Println("!", i)
        if stack[i][0] != -1 {
            return stack[i]
        }
    }
    return nil
}

func Det(mas []Triplet, Final []int, q int) {
    n := len(mas)
    l:=1
    z:=make([]int, n)
    for i:=0; i<n; i++ {
        z[i] = -1
    }
    z[0] = q
    qo := Closure(mas, z)
    delta := make([]Pair, n)
    for i:=0; i<n; i++ {
        delta[i].one = append(delta[i].one, -1)
    }
    F := make([][]int, n, n)
    for i:=0; i<n; i++ {
        F[i] = make([]int, n)
    }
    for i:=0; i<n; i++ {
        for j:=0; j<n; j++ {
            F[i][j] = -1
        }
    }
    Q := make([][]int, n, n)
    for i:=0; i<n; i++ {
        Q[i] = make([]int, n)
    }
    for i:=0; i<n; i++ {
        for j:=0; j<n; j++ {
            Q[i][j] = -1
        }
    }
    for i:=0; i<len(qo); i++ {
        Q[0][i] = qo[i]
        //fmt.Println(Q[i])
    }
    stack := newStack(n)
    for i:=0; i<len(qo); i++ {
        stack[0][i] = qo[i]
    }
    stackSize := 1
    for stackSize > 0 {
        zz := Pop(stack)
        fmt.Println("zz = ",zz)
        for u:=0; u<len(zz); u++ {
            if Final[u] == 1 {
                for i:=0; i<len(F); i++ {
                    if F[i][0] != -1 {
                        F[i] = zz
                        break
                    }
                }
                break
            }
        }
        hh := make([]int, n)
        for i:=0; i<n; i++ {
            hh[i] = -1
        }
        start:=0
        for a:=0; a<n; a++ {
            help := mas[a].third
            for i := 0; i < n; i++ {
                if help == mas[i].third && Search(zz, mas[i].first){
                    hh[start] = mas[i].second
                    start++
                }
            }
            //fmt.Println("hh[", help, "] = ", hh)

            zzz := Closure(mas, hh)
            eq := true
            for i := 0; i < n; i++ {
                for j := 0; j < n; j++ {
                    if zzz[j] != Q[i][j] {
                        eq = false
                    } else {
                        eq = true
                    }
                }
            }
            if !eq {
                for i := 0; i < n; i++ {
                    if Q[i][0] != -1 {
                        for j := 0; j < len(zzz); j++ {
                            Q[i][j] = zzz[j]
                        }
                    }
                }
                for i := 0; i < len(zzz); i++ {
                    stack[stackSize][i] = zzz[i]
                }
            }
            fmt.Println("!!!!!!!!!!!a = ", a)
            fmt.Println("help = ", help)
            fmt.Println("zzz = ", zzz)
            delta[0].one = zz
            delta[0].two = "hren"
            fmt.Println("l = ", l)
            if l < n {
                delta[l].one = zzz
                delta[l].two = help
                l++
            }
            for i:=0; i<n; i++ {
                hh[i] = -1
            }
            start = 0
            stackSize--
        }
    }
    for i:=0; i<n; i++ {
        for j:=0; j<n; j++ {
            if delta[i].one[j] != -1 {
                fmt.Print(delta[i].one[j], " ")
            }
        }
        fmt.Print(delta[i].two, " ")
        fmt.Println()
    }
    //fmt.Println("det : ", delta)

}

func main() {
    var n, m, q int

    fmt.Scan(&n)
    fmt.Scan(&m)

    mas := make([]Triplet, m)

    for i:=0; i<m; i++ {
        fmt.Scan(&mas[i].first)
        fmt.Scan(&mas[i].second)
        fmt.Scan(&mas[i].third)
    }

    final := make([]int, n)

    for i:=0; i<n; i++ {
        fmt.Scan(&final[i])
    }
    fmt.Scan(&q)

    //PrintMe(mas, n, m, final)

    //C:= Closure(mas, n, z)
    //fmt.Print("C = ",C)
    Det(mas, final, q)
}