Hide

Problem B
Join Strings

You are given a collection of N non-empty strings, denoted by S1,S2,,Sn. Then you are given N-1 operations which you execute in the order they are given. The ith operation is has the following format: ‘a b’ (1-based indexing, without the quotes), which means that you have to make the following changes:

  1. Sa=Sa+Sb, i.e. concatenate ath string and bth string and store the result in ath string,

  2. Sb = "", i.e. make the bth string empty, after doing the previous step.

You are ensured that after the ith operation, there will be no future operation that will be accessing Sb. Given these operations to join strings, print the last string that will remain at the end of this process.

Input

The first line contains an integer N (1N105) denoting the number of strings given. Each of the next N lines contains a string denoting the Si. All the characters in the string Si are lowercase alphabets from ‘a’ to ‘z’. The total number of characters over all the strings is at most 106, i.e i=1N|Si|106, where |Si| denotes the length of the ith string. After these N strings, each of the next N-1 lines contain two integers a and b, such that ab and 1a,bN denoting the ith operation.

Output

Print the last string which remains at the end of the N-1 operations.

Warning

The I/O files are large. Please use fast I/O methods.

Sample Input 1 Sample Output 1
4
cute
cat
kattis
is
3 2
4 1
3 4
kattiscatiscute
Sample Input 2 Sample Output 2
3
howis
this
practicalexam
1 2
1 3
howisthispracticalexam
Hide

Please log in to submit a solution to this problem

Log in