쪽지

이미지 출처: flickr.com

어린 Jón은 어린 Gunna에게 푹 빠져 있다. 그는 학교에서 수업을 받는 도중에 그녀에게 쪽지를 보내려고 한다. 쪽지가 Jón에게서 Gunna에게 가려면 여러 학생의 손을 거쳐야 한다. 또한 선생님이 쪽지를 보고 빼앗을 위험도 있다. Jón은 반 친구들이나 심지어 선생님이 쪽지의 메시지를 읽을까 봐 걱정한다.

그래서 Jón은 새로운 암호화 방법을 고안했다. 그가 가장 먼저 하는 일은 메시지를 뒤집는 것이다. 그러면 메시지를 읽기가 훨씬 어려워지기 때문이다. 이 방법을 더 안전하게 만들기 위해 그는 매번 메시지의 작은 부분만 보내므로 쪽지를 여러 장 보내야 한다. 그런 다음 이 쪽지들을 역순으로 보낸다. Jón은 자신이 정말 영리하다고 생각한다.

연애편지를 쓰는 데 사용된 암호화 방법을 전혀 모르는 채로 연애편지를 받아 본 적이 없는 사람이 어디 있겠는가? Gunna가 바로 그런 일을 겪었다. 따라서 그녀는 원래 메시지를 읽을 수 없다. 그래서 Gunna는 교실에 $n$장의 쪽지를 들고 앉아 있으며, 그 내용을 이해하려면 쪽지들을 이어 맞춰야 한다. 그녀가 아는 것은 각 쪽지에 무엇이 적혀 있는지와 쪽지들이 어떤 순서로 도착했는지뿐이다. Gunna가 메시지를 읽을 수 있도록 도와줄 수 있는가?

점수

그룹 | 점수 | 제한

1 | 50 | $n \leq 100$, 원래 메시지의 문자 수는 최대 $1\,000$

2 | 50 | 추가 제한 없음

입력의 첫째 줄에는 쪽지의 수를 나타내는 하나의 정수 $1 \leq n \leq 2 \cdot 10^6$이 주어진다. 다음 $n$개의 줄에는 각각 하나의 문자열이 주어지며, 각 쪽지에 적힌 내용이 Gunna에게 도착한 순서대로 주어진다. 원래 메시지의 문자 수는 최대 $2 \cdot 10^6$이다. 메시지는 영문 소문자로만 이루어져 있으며 공백은 없다. 모든 쪽지에는 적어도 하나의 문자가 들어 있다.

Jón이 Gunna에게 보내려고 했던 원래 메시지를 한 줄에 출력한다.