변덕스러운 정렬 timer 10s memory 1024MB

우리는 영문 대문자로 이루어진 문자열을 만들고 싶다. 하지만 문자열의 문자들이 항상 오름차순으로만 증가하는 것이 아니라, 어떤 구간에서는 엄격히 증가하고 어떤 구간에서는 엄격히 감소하도록 만들고 싶다.

문자열의 첫 글자는 반드시 A여야 한다. 그 다음에는 하나 이상의 블록(block)으로 이루어져야 한다. i번째 블록은 정확히 \mathbf{L_i}개의 문자를 포함해야 한다. i가 홀수인 블록에서는, 그 블록의 각 문자는 문자열에서 바로 앞선 문자보다 알파벳 순서로 뒤에 와야 한다. 반대로 i가 짝수인 블록에서는, 그 블록의 각 문자는 문자열에서 바로 앞선 문자보다 알파벳 순서로 앞에 와야 한다. 블록의 첫 글자도 "바로 앞선 문자"가 존재한다는 점에 유의하라(그 문자는 블록 밖에 있을 수도 있다). 이 모든 규칙을 만족하는 문자열을 유효(valid)하다고 한다. 유효한 문자열은 여러 개일 수 있으며, 그중 사전순(알파벳 순)으로 가장 앞서는 문자열을 찾고자 한다.

예를 들어 블록이 2개이고 크기가 \mathbf{L_1}=2, \mathbf{L_2}=3이라면, 문자열은 총 1+\mathbf{L_1}+\mathbf{L_2}=1+2+3=6글자여야 한다(1은 처음의 A를 위한 것이다). XYZYBA, AZYCBA, AYZYBB는 각각 시작 글자 조건, 첫 번째 블록의 정렬 조건, 두 번째 블록의 정렬 조건을 위반하므로 유효하지 않다. AYZYBA는 유효하다. 또한 ABDCBA 역시 유효하며, 게다가 유효한 문자열들 중 사전순으로 가장 앞서는 문자열이다.

각 블록의 크기가 주어질 때, 모든 유효한 문자열 중 사전순으로 가장 앞서는 유효한 문자열을 출력하라. 주어진 제한 내의 모든 입력에 대해, 유효한 문자열이 적어도 하나는 존재함을 보일 수 있다.