You and your friends have found yourself in a house with ~n~ rooms, each one linked to a different room by a portal, and one is the exit. You are eager to compete with each other to find out who is the coolest, so you've decided to pick different starting rooms and race to the end. From your starting rooms, each of you will follow the portal to a different room once a turn until you either reach the exit, or get stuck in the portal maze forever...

Input

The first line contains to integers ~n, m\ (1\leq n,m\leq 10^4)~, where ~n~ represents the number of portal rooms, and ~m~ represents the number of friends there are competing in a race.

The rooms are labelled ~1~ through to ~n~, and ~n~ is the exit of the race. The next line contains ~n-1~ integers ~a_i\ (1 \leq a_i \leq n)~, where each ~a_i~ represents the room that the portal in the ~i~th room is connected to. The final ~n~th room doesn't connect to any other rooms (it is the exit), hence line only contains ~n-1~ values.

The next line contains ~m~ strings ~S_i\ (1 \leq S_i.\text{length} \leq 10^4)~ separated by spaces, where ~S_i~ is the name of the ~i~th friend. Each name contains only upper and lower case english characters, and digits 0-9.

The final line contains ~m~ integers ~b_i\ (1\leq b_i \leq n-1)~. Each integer represents the room which the ~i~th friend will begin at in the race. No one can start at the exit, that'd be too easy.

Output

On the first line, output the names of the people who reached the end (room ~n~) in order of the number of turns it took them to reach it, so the person who reached the end quickest is at the start of the line and the slowest at the end of the line. The names should be separated by spaces.

On the second line, output the names of the people who never reached the end.

In the case of a tie in the first line, and for all names in the second line, output them in the order in which they appeared in the input i.e. their number ~i~.

Example

Input 1

4 3
2 3 4
Shaun Jamie Kevin
1 2 3

Output 1

Kevin Jamie Shaun

Kevin reaches the end in one turn, Jame in two, and Shaun in 3. Since everyone makes it to the end, the second output line is blank.

Input 2

4 3
2 3 1
John James Jerry
1 2 3

Output 2

John James Jerry

In this portal room layout, the first 3 rooms all cycle, so there is no way to reach the end. Thus, no one makes it to the end and all three names are printed out (in input order) in the second output line.

Input 3

4 4
1 3 4
Patrick Billy Bob Alex
2 3 1 3

Output 3

Billy Alex Patrick
Bob

Billy and Alex both escape in a single turn, which Patrick takes 2 turns. Since Billy appeared first in the input he is printed first. Bob gets caught portalling from room 1 to room 1 forever, so he is printed on the second line.