시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 512 MB 290 65 48 25.806%

문제

길이가 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'를 순서대로 출력한다.

예제 입력 1

5
ba
a
abab
a
aba
baba
ab
aba

예제 출력 1

ababa
SPPSPSPS

예제 입력 2

3
a
aa
aa
a

예제 출력 2

aaa
PPSS

예제 입력 3

2
a
c

예제 출력 3

ac
PS

힌트

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

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

  • h
  • he
  • hel
  • hell
  • hello

접미사는 다음과 같다.

  • o
  • lo
  • llo
  • ello
  • hello

출처