신촌 통폐합 계획

극단적인 출산율 감소로 신촌 지역의 $N$개 대학교가 하나의 학교로 통합되었다.

긴 회의 끝에 통합 학교의 이름은 $N$개 대학교의 이름을 이어 붙여서 정해졌다. 회의에서 이름을 정한 방법은 다음과 같다.

$N$개 대학교의 이름 $s_1, s_2, \cdots, s_N$을 일렬로 나열한다. 그다음 아래 과정을 $N - 1$번 반복한다.

1. $s_i$와 $s_j$가 모두 빈 문자열이 아닌, 서로 다른 두 정수 $i, j$를 고른다.
2. $s_i$의 뒤에 $s_j$를 이어 붙인다.
3. $s_j$를 빈 문자열로 바꾼다.

모든 과정이 끝나면 빈 문자열이 아닌 $s_k$가 하나 남는다. 이 $s_k$가 통합 학교의 이름이 된다.

$N$개 대학교의 이름 $s_1, s_2, \cdots, s_N$과 회의에서 순서대로 고른 $i, j$가 주어질 때, 회의에서 정해진 통합 학교의 이름을 구하는 프로그램을 작성하시오.

첫 번째 줄에 대학교의 개수 $N$이 주어진다. ($2 \leq N \leq 500\,000$)

다음 $N$개 줄의 $i$번째 줄에는 알파벳 소문자로 이루어진 대학교 이름 $s_i$가 주어진다. 주어지는 대학교 이름의 길이 합은 $500\,000$을 넘지 않는다.

다음 $N - 1$개 줄에는 회의에서 고른 $i, j$가 공백을 사이에 두고 차례로 주어진다. ($1 \leq i, j \leq N$, $i \neq j$)

주어진 순서대로 회의를 진행하면 $s_i$와 $s_j$는 항상 빈 문자열이 아니다.

첫 번째 줄에 회의를 통해 정해진 통합 학교의 이름을 출력한다.