암호 키

국가와 국경, 그리고 국가 사이에 주기적으로 일어나는 분쟁이 존재해 온 수백 년 동안 첩보 체계도 함께 존재해 왔다. 한 나라에 불법 또는 합법으로 거주하는 요원은 국가 기밀을 담은 보고를 다른 나라로 보낸다. 보고를 전달하는 방법은 끊임없이 바뀌어 왔다. 백 년 전에는 종이 편지였고, 오십 년 전에는 무선 전문이었으며, 지금은 전자 우편으로도 보고를 보낼 수 있다. 그러나 모든 보고에 공통된 한 가지 특징은 변하지 않았고 앞으로도 변하지 않을 것이다. 어떤 정보 메시지든 가로챌 수 있다는 점이다. 이런 가능성에 대비하기 위해 보고는 정해진 수신자만 읽을 수 있도록 암호화된다. 이때 보통 키를 사용하는데, 키란 보고를 복호화할 수 있게 해 주는, 흔히 의미가 없는 비교적 짧은 문자열이다. 또한 요원이 붙잡혔을 때 관계자에게 키를 알려 주지 못하도록 각 보고에는 그 보고만의 키가 대응하며, 이 키는 보고와 함께 전송되는데 그 역시 그리 복잡하지 않은 방식으로 암호화된다. 여러분은 어떤 암호화 알고리즘에 대해 암호화된 키로부터 원래 키를 얻는 방법을 구현해야 한다.

비어 있지 않은 키 s를 암호화하기 위해 요원은 먼저 문자열 s가 문자열 t의 접두사이고 뒤집은 문자열 s가 문자열 t의 접미사인 문자열 t를 고른다. 이때 문자열 t에는 문자열 s와 관계없는 문자들이 있을 수 있다. 그다음 문자열 t의 왼쪽에 임의의 (0일 수도 있는) 개수만큼 임의의 문자를 덧붙이고, 오른쪽에도 정확히 같은 개수만큼, 어쩌면 다른 임의의 문자를 덧붙인다. 이제 문자열 t가 키 s의 암호화된 형태이다.

키, 즉 원래 문자열 s를 복원하려 할 때 여러 가지 경우가 나올 수 있다는 것은 분명하다. 그래서 가능한 모든 후보 중에서 키는 가장 긴 문자열이어야 하고, 그러한 문자열이 여러 개라면 무작위로 왼쪽과 오른쪽에 덧붙인 문자의 개수가 최소인 문자열, 즉 문자열 t의 길이가 최대인 문자열이어야 한다고 정했다. 여러분은 암호화된 형태로부터 키 s를 복원하는 알고리즘을 구현해야 한다.

첫 번째 줄에는 복호화해야 할 키의 개수 n이 정수로 주어진다. 다음 n개의 줄에는 찾아야 할 키의 암호화된 형태가 한 줄에 하나씩 주어진다. 각 암호화된 형태는 라틴 알파벳 소문자로만 이루어져 있다. 모든 암호화된 키의 길이 합은 100000자를 넘지 않는다. 각 암호화된 형태마다 조건을 만족하는 비어 있지 않은 키가 적어도 하나 존재한다고 보장된다.

복호화된 키 n개를 한 줄에 하나씩 출력한다.