게놈 팰린드롬

비밀 생물학 연구 덕분에 박테리아의 DNA에 암호화된 메시지를 삽입할 수 있게 되었다. DNA 염기 서열은 $A$, $C$, $G$, $T$ 문자로 표현되므로, 메시지는 이 문자로 이루어진 문자열로 나타낼 수 있다.

만들어진 박테리아의 수명을 늘리려면 메시지가 팰린드롬이어야 한다. 즉, 앞에서 읽든 뒤에서 읽든 같아야 한다. 예를 들어 "A", "ACA", "ATTTGTTTA"는 팰린드롬이고, "ATGT"와 "CACA"는 팰린드롬이 아니다.

현재 맡은 작업은 길이가 $n$인 팰린드롬 메시지를 사전순으로 나열했을 때 $k$번째에 오는 메시지를 구하는 것이다. 문자열 $s_1s_2\ldots s_n$이 $t_1t_2\ldots t_n$보다 사전순으로 작다는 것은, 어떤 $i$에 대해 $s_1 = t_1, s_2 = t_2, \ldots, s_{i-1} = t_{i-1}$이고 $s_i < t_i$인 경우를 말한다.

첫 줄에 정수 $n$과 $k$가 공백으로 구분되어 주어진다 ($1 \le n \le 100$, $1 \le k \le 10^{18}$).

길이가 $n$인 팰린드롬 중 사전순으로 $k$번째 메시지를 한 줄에 출력한다. 그런 메시지가 없으면 "Impossible"을 출력한다.