시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
4 초 512 MB 22 6 6 30.000%

문제

지훈이는 평소에 자주 들어가지 않는 어떤 사이트에 오랜만에 들어가려고 했는데, 비밀번호를 잊어버렸다는 사실을 깨달아 버렸다!

그래서 지훈이는 비밀번호 찾기를 하려고 하였으나, 그 사이트는 암호를 hash 를 이용하여 관리하기 때문에, 지훈이가 잃어버렸던 비밀번호를 다시 복구하지는 못하고, 새로 비밀번호를 만들라고 하였다. 그 사이트는 보안을 철저하게 하는 사이트였기 때문에, 비밀번호를 정할 때 다음과 같은 조건을 충족시킬 것을 의무화하고 있다.

  • 비밀번호의 길이는 A 이상이어야 한다.
  • 비밀번호에 숫자는 B 글자 이상 있어야 한다.
  • 비밀번호에 특수 문자(숫자나 알파벳이 아닌 문자)는 C 개 이상 있어야 한다.
  • 비밀번호에 알파벳 대문자는 D 개 이상 있어야 한다.

그래서 지훈이는 다음과 같은 과정으로 비밀번호를 만들려고 한다.

  1. 임의로 글자(여기서 글자는 알파벳 대소문자, 숫자, 특수문자!@#$%^&*()_-를 의미한다)를 N 개 생성하여 문자열을 만든다.
  2. 총 N(N-1)/2 개의 연속부분문자열들이 존재할텐데, 하나씩 살펴보면서 위 조건을 만족하는 경우에만 후보 리스트에 넣어 둔다. 이 때 똑같은 연속부분문자열이 두 번 이상 등장하더라도 한 번만 고려한다. (ex - “abab”에서 “ab”는 후보 리스트에 한 개만 들어있음)
  3. 후보 리스트에 든 연속부분문자열들을 사전순으로 정렬한다.
  4. 후보 리스트에 든 연속부분문자열의 개수가 M 이고, candidate[1 ~ M]에 저장되어 있을 때, candidate[(M+1)/2] 을 최종 비밀번호로 채택한다.

지훈이는 길이 N 의 문자열을 작성했는데, 비밀번호의 조건이 너무 까다로운 나머지 비밀번호로 어떤 것이 채택될 지 알 수가 없어서 여러분에게 비밀번호를 구해 달라고 요청했다. 지훈이가 쓴 길이 N 의 문자열이 주어질 때, 지훈이가 최종적으로 채택할 비밀번호를 출력하라. (N <= 500000)

입력

첫째 줄에 N,A,B,C,D 가 띄어쓰기로 구분되어 차례대로 주어진다. (N, A 는 자연수, B,C,D 는 음이 아닌 정수이다.)

둘째 줄에 지훈이가 쓴 길이 N 의 문자열이 주어진다.

출력

지훈이가 최종적으로 채택하게 될 비밀번호를 출력한다. 답이 항상 존재하는 경우만 주어진다.

예제 입력

10 9 1 0 1
h4llowOrld

예제 출력

h4llowOrl

힌트