Sleepy Alice is a new student who just started her freshman year at the University of St Andrews. She lives in one of the student accommodation halls and has to walk to the School of Computer Science every day for lectures / lab sessions etc. As you all probably know already, there are many routes she can take.

Sleepy Alice is a new student who just started her freshman year at the University of St Andrews. She lives in one of the student accommodation halls and has to walk to the School of Computer Science every day for lectures / lab sessions etc. As you all probably know already, there are many routes she can take.

On some days, she has lectures very early in the morning, and on some days she only has an afternoon lab session. Alice (like many computer science students) doesn’t like to wake up early, (thus nicknamed Sleepy Alice) and therefore wants to optimize her time by taking the fastest route from the halls to the school on days when she has morning lectures.

On the other hand, she also likes to explore the little town of St Andrews as much as she can.  Since she is lazy, she doesn’t want to go out walking just for the sake of exploring without a second reason. Therefore, she has decided that on the days she has only an afternoon lab session; she will take the slowest route to the school so that she can spend as much time outdoors, without going through the same place twice.

Bob is a second year student who wants to impress Alice. He has decided to help her by creating writing a program that would tell Alice how many minutes earlier she must leave her hall in order to arrive at the school without missing any part of her lectures or lab sessions. Can you help Bob develop this program?

Input

The first line will contain N (1 <= N <= 100): the number of place in St Andrews
The second line will contain the names of N places, separated by a space. The first place is the student halls where Alice lives in. The last place is her destination.
The third line will contain E (1<=E<=1000): the number of different routes connecting the places.
The next E lines will contain two places and the time to walk between them T (1 <= T <= 1000000) separated by spaces.
Note that all routes are two way roads.

Output

Two lines containing how early Alice should leave her halls of residence, namely:
The time it would take her to reach the school on a day with morning lectures
The time it would take her to reach the school on a day with only afternoon lab sessions

Example

Input:
4
dra union scores school
5
dra union 20
dra scores 30
union school 5
union scores 20
scores school 30

Output:
25
70

Explanation:
dra > union (20) + union > school (5) = 25
dra > scores (30) + scores > union (20) + union > school (5) = 55
dra > scores (30) + scores > school (30) = 60
dra > union (20) + union > scores (20) + scores > school (30) = 70
…
…
Note that routes such as:
dra > scores(30) + scores > dra(30) + dra > union(20) + union > school(5) = 85
also exist but is not a valid answer as this involves going through dra twice.