16925번 - 문자열 추측 스페셜 저지

길이가 N인 문자열 S가 있다. S는 알파벳 소문자로만 이루어져 있다.

문자열 S의 길이가 N-1이하인 모든 접두사와 접미사를 이용해, 원래 문자열 S를 만들어보려고 한다. S의 모든 접두사와 접미사가 주어졌을 때, 원래 문자열 S가 무엇인지 구하는 프로그램을 작성하시오.

첫째 줄에 문자열 S의 길이 N(2 ≤ N ≤ 100)이 주어진다. 다음 2N-2개의 줄에 걸쳐서 문자열 S의 접두사와 접미사가 한 줄에 하나씩 주어진다. 모든 접두사와 접미사가 주어지기 때문에, 길이가 i(1 ≤ i ≤ N-1)인 문자열의 개수는 항상 2개이다.

첫째 줄에 입력으로 주어진 접두사와 접미사를 이용해 만들 수 있는 문자열 S를 출력한다.

둘째 줄에는 입력으로 주어진 문자열이 접두사이면 'P', 접미사이면 'S'를 순서대로 출력한다.

문자열 S의 접두사는 S의 부분 문자열 중에서 시작이 첫 번째 문자인 것이고, 접미사는 끝이 마지막 문자인 것이다.

S = "hello"인 경우 접두사는 다음과 같이 5가지가 있다.

• h
• he
• hel
• hell
• hello

접미사는 다음과 같다.

• o
• lo
• llo
• ello
• hello