시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 1024 MB (추가 메모리 없음)84312542.373%

문제

미소가 사는 마을에는 $N$채의 집이 일렬로 있다. 어느 날 밤, 마을 내 모두가 잠든 사이에 집마다 폭탄 혹은 폭탄 쉴드가 배치되었다. 폭탄과 폭탄 쉴드는 다음과 같은 특징이 있다.

  • 폭탄은 알파벳 대문자로 표현되며 폭탄을 막을 수 있는 폭탄 쉴드는 폭탄의 알파벳에 대응되는 알파벳 소문자로 표현된다. 
  • 폭탄은 설치된 위치 기준으로 해당 집을 포함하여 $1$칸 좌측에 있는 집과 $1$칸 우측에 있는 집이 터지며 폭탄에 대응되는 쉴드가 있는 집은 터지지 않는다. 예를 들어 폭탄 B가 터진다고 할 때, 배치가 ABc인 경우 모든 집이 터지지만, 배치가 ABb인 경우 마지막 집은 터지지 않는다.

다행히도 터지는 폭탄의 종류는 $1$ 가지 일 때, 폭탄이 터지기 전까지 미소가 마을에 설치된 폭탄과 폭탄 쉴드들을 재배치하여 마을의 피해를 최소화할 수 있도록 도와주자! 만약 피해를 최소화할 수 있는 배치가 여러 개라면 사전 순으로 가장 앞서는 배치를 출력한다.

입력

첫 번째 줄에 집의 개수 $N$과 터지는 폭탄의 종류 $B$가 주어진다. ($1 \le N \le 100\,000$)

두 번째 줄에 알파벳 소문자, 대문자로 이루어진 현재 배치 $S$가 주어진다. 

현재 배치 $S$에는 터지는 폭탄이 $1$개 이상 존재한다.

출력

피해를 최소화할 수 있는 배치를 출력한다. 만약, 피해를 최소화할 수 있는 배치가 여러 개라면 사전 순으로 가장 앞서는 배치를 출력한다.

단, 아스키코드에서 대문자는 소문자보다 작으므로 사전 순으로 앞에 온다. 예를 들어, "ABab"는 "AaBb"보다 사전 순으로 앞서는 문자열이다.

예제 입력 1

6 C
AdCAeF

예제 출력 1

AAFdeC

예제 입력 2

6 B
BaBcab

예제 출력 2

BBbaac

예제 입력 3

5 D
EFDdA

예제 출력 3

AEFdD

출처

University > 홍익대학교 > 2021 홍익대학교 프로그래밍 경진대회 I번