Problem 6: State-Machine

State-Machine

Your task is to generate a Statemachine given in the input. Statemachines can be displayed as a graph. You have to run through a Text-string I.

Each State S has an Integer ID as indentifier for this State/Node. Transitions go from one state to the next one and have a Character C assigned. Each State can have as many Transitions as the Lower- and Uppercase-Alphabet have (26 Uppercase Letters + 26 Lowercase Letters). The Input I describes the transitions to take, beginning at state ID=0.

You can assume that each transition is valid and that the program will not end in a "dead-end", where the program can't escape. But the graph can still have nodes with no successor. Transitions from one node to itself are allowed.

Input

The first line contains the amount of transitions N.
The next N lines each contain a transition from one node to the next.
The Transitions have the following blueprint: "ID_Out -- C --> ID_Target"
Where each ID_Out is the id of the current node, C the character of the transition and ID_Target the following node.
The last Line contains the input I.

1 <= N <= 1000000
0 <= ID <= 100000
C ∈ {a,b,...,z,A,B,...,Z}
I = Inputlength < 1000

Output

The ID of the last state after running through the statemachine.

Example

Input

    10
    0 -- I --> 0
    0 -- E --> 0
    2 -- S --> 0
    0 -- i --> 1
    0 -- u --> 1
    2 -- e --> 1
    1 -- s --> 2
    2 -- t --> 2
    1 -- p --> 2
    1 -- r --> 2
    IEEEistSuper

IEEE SB Passau Advent Calendar 2025