26080번 - 곰곰이와 하카타

곰곰이가 컴퓨터를 하고있는데, 무엇을 보고 있는걸까요? 뭘 보고있는지는 모르겠지만, 총총이 몰래 비밀스럽게 보는 걸 보니 떳떳하진 않은가봐요.

참다못한 총총이가 소리를 내네요.

총총이가 단단히 화가 났나봐요. 사실 곰곰이는 저번에 노란색 장난감 칼을 들고 싸우는 영상을 몰래 보다가 들킨 적이 있었거든요.

총총이는 이런 곰곰이가 못마땅하지만, 즐거운 하카타 여행을 위해 곰곰이를 용서해주기로 했어요. 단, 하카타까지 전용기를 조종해 주면요.

곰곰이와 총총이는 전용기를 타고 하카타로 여행을 가요. 이 비행기는 아래 조건을 만족하면서 비행을 해요.

• 비행기는 인천 공항에서 이륙해서, 후쿠오카 공항에 착륙할 때까지 중간의 어떠한 지점에도 착륙하지 않아요. 비행기의 고도가 0이 되면 착륙했다고 가정해요.
• 비행기는 수평으로 d만큼 이동하고, d만큼 떨어진 지점인 후쿠오카 공항에 착륙해요.
• 비행기는 인천 공항에서 후쿠오카 공항까지 일직선으로 날아가요.
• 각 공항의 고도는 0이며, 중간에 장애물이 없어요.

곰곰이는 비행기를 조종하기 싫어서 자동 조종장치가 없나 찾아보았더니, 있었습니다. 이 비행기는 자동 조종 장치에 A와 D 둘 중 하나를 입력할 수 있어요.

• 자동 조종장치에 A를 입력하면 수평 거리 1만큼 이동할 때 고도가 1만큼 증가해요.
• 자동 조종장치에 D를 입력하면 수평 거리 1만큼 이동할 때 고도가 1만큼 감소해요.

자동 조종장치에 입력한 순서대로 비행기의 자동 조종장치가 비행기를 안전하게 조종할 거예요. 예를 들어, 자동 조종장치에 AD를 입력했다면, 고도가 1만큼 올라간 다음에, 고도가 1만큼 내려가게 됩니다. 즉, 수평거리 2만큼 이동해서 착륙하게 됩니다.

하카타까지의 비행을 위해, 곰곰이는 관제사에게 허가를 요청하였습니다. 그랬더니 관제사는 비행할 수 있는 가짓수 중 사전순 k번째만 허가하였습니다. 곰곰이는 자동 조종장치에 어떻게 입력을 해야 할까요? 하카타에 가서 즐거운 여행을 하고 싶은 곰곰이는 여러분에게 도움을 요청하였습니다. 곰곰이를 도와주세요.

첫 줄에 정수 d와 k가 공백으로 구분되어 주어집니다.

문제에 대한 답을 출력해 주세요. 그러한 것이 없는 경우 -1을 출력해 주세요.

• 1 ≤ d ≤ 2 × 10⁵
• d는 짝수입니다.
• 1 ≤ k ≤ 10¹⁸

문제에 따르면, 출력해야 하는 문자열은 A, 혹은 D로만 이루어진 길이 d의 문자열을 출력하는 것입니다.

길이 d의 문자열 A가 길이 d의 문자열 B보다 사전순으로 앞선다는 것은 다음 두 조건 중 하나를 만족함을 의미합니다.

• a₁ < b₁ 입니다.
• a₁ = b₁, ... , a_i-1 = b_i-1이고 a_i < b_i인 i가 존재합니다. (i는 2이상 d이하 정수입니다.)

또한 문자 A는 문자 D보다 사전순으로 앞섭니다. 즉 문자 A < 문자 D를 만족합니다.