너무 많은 하이픈

Donald Knuth와 Leslie Lamport가 개발한 TeX와 LaTeX 같은 문서 마크업 언어는 논문, 과학 문서, 프로그래밍 올림피아드 문제 지문 조판에 자주 쓰입니다. 이 언어들은 키보드에 없는 문자를 입력할 수 있도록 특수 매크로를 제공합니다. 예를 들어 하이픈이 여러 개 연속으로 나오면 길이가 다른 대시로 바뀝니다. 그래서 문서에 하이픈이 여러 개 이어진 줄을 넣으려면 특별한 조치를 취해야 합니다.

이때 중괄호를 쓰면 연속된 하이픈 묶음이 매크로로 해석되지 않도록 막을 수 있습니다. C++ 같은 많은 언어와 마찬가지로, TeX에서도 중괄호로 문자 블록을 묶습니다. 중괄호는 올바른 괄호 순서를 이루어야 합니다. 즉 중괄호 외의 문자를 모두 지운 뒤, 여는 중괄호 {는 +1, 닫는 중괄호 }는 -1로 바꾸면, 결과 수열의 합은 0이고 모든 접두사의 합은 0 이상이어야 합니다.

하이픈 연속이 대시로 바뀌지 않으려면 연속한 두 하이픈 사이에 중괄호가 최소 하나 있어야 합니다. 플러스 기호는 연속해도 매크로에 해당하지 않으므로 연속한 플러스에는 추가 조건이 없습니다.

플러스와 하이픈으로 이루어진 문자열 $s$에 위 규칙을 지키며 중괄호를 최소 개수로 추가해서 연속한 하이픈이 없는 문자열을 만듭니다. 이 결과 문자열을 $s$의 최적 이스케이프 문자열이라고 합니다.

예를 들어 ++-{-}에 대한 최적 이스케이프 문자열은 정확히 다섯 개입니다. ++-{-}, ++-{-}, ++{-}-, +{+-}-, {++-}-. 사전순은 처음으로 다른 문자를 기준으로 비교하며, 문자 순서는 + < - < { < }입니다.

$s$의 모든 최적 이스케이프 문자열을 사전순으로 나열했을 때 k번째 문자열을 구하세요. k가 최적 이스케이프 문자열의 개수보다 크면 그 사실을 알려야 합니다.

첫 줄에 +와 -로 이루어진 문자열 $s$가 주어집니다. $s$는 비어 있지 않고 길이는 60 이하입니다. 둘째 줄에 정수 $k$ ($1 \le k \le 10^{18}$)가 주어집니다.

$s$의 최적 이스케이프 문자열 중 사전순으로 k번째 문자열을 출력합니다. k가 최적 이스케이프 문자열의 개수보다 크면 Overflow를 출력합니다.