증가하며 중복 없는 문자열

소문자 알파벳으로 이루어진 문자열에서 이웃한 두 문자가 같은 자리가 하나도 없으면 그 문자열을 중복 없는 문자열이라고 한다.

1 이상 k 이하인 모든 j에 대해 정확히 j번 등장하는 문자가 하나씩 있고 문자열의 길이가 $1+2+3+\cdots+(k-1)+k$이면 그 문자열을 k-증가 문자열이라고 한다. 예를 들어 k = 3이면 3-증가 문자열에는 한 번 등장하는 문자, 두 번 등장하는 문자, 세 번 등장하는 문자가 순서에 관계없이 하나씩 있고 전체 길이는 6이다.

두 조건을 모두 만족하는 문자열이 k-증가이면서 중복 없는 문자열이다. k를 하나 고정하고 그런 문자열을 모두 사전순으로 늘어놓는다고 하자. 두 가지 예는 다음과 같다.

k = 2: aba, aca, ada, ..., aya, aza, bab, bcb, bdb, ..., zxz, zyz

k = 3: ababac, ababad, ..., ababay, ababaz, ababca, ..., zyzyzx

k-증가이면서 중복 없는 문자열을 사전순으로 정렬한 목록에서 n번째 문자열은 무엇인가?

입력은 테스트 케이스 한 개로 이루어진다. 이 프로그램은 서로 다른 입력으로 여러 번 실행될 수 있다. 입력은 한 줄이고 두 정수 k와 n이 주어진다 ($1 \le k \le 26$, $1 \le n \le 10^{18}$). k-증가이면서 중복 없는 문자열을 사전순으로 정렬한 목록에서 n번째 문자열을 구하라는 뜻이다.

사전순으로 정렬한 목록에서 n번째 k-증가 중복 없는 문자열을 출력한다. 그런 문자열이 없으면 -1을 출력한다.