23328번 - 마을 구하기

문제

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

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

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

입력

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

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

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

출력

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

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

제한

힌트