𝘒주년

처음 "Hello, world!"가 출력되던 그날, 설레는 마음으로 NYPC에 도전했던 순간을 기억하시나요? 2016년, 넥슨은 ‘코딩으로 세상을 바꿀 수 있다’는 믿음으로 NYPC라는 여정을 시작했습니다. 그리고 지난 10년 간, 약 $4$만 명의 청소년들이 NYPC에 도전하며 ‘세상을 바꾸는 코딩’을 함께 했습니다.

$1$부터 $N$까지 모든 정수를 다음 규칙에 따라 우리말로 표현한 후, 각각의 수 뒤에 공백 없이 주년을 붙이고 사전 순으로 정렬했을 때, $K$번째에 오는 수를 출력하는 프로그램을 작성하라. 주년을 붙인 뒤에 정렬한다는 데 유의하라.

두 단어에 대해서 사전 순으로 앞에 오는 단어는, 이 단어들을 나란히 놓고 왼쪽부터 읽으면서 처음으로 다른 글자가 나왔을 때 가나다순으로 앞에 있는 글자가 포함된 단어가 사전 순으로 앞에 오는 단어다. 이때, 다른 글자가 나오기 전에 단어가 끝난다면, 길이가 더 짧은 단어가 사전 순으로 앞에 온다.

각 자리의 수는 우리말로 다음과 같이 표현한다.

추가로 다음과 같은 규칙을 따른다.

• 띄어쓰기는 사용하지 않는다.
• 기본적으로 $4$자리 단위(만, 억, 조)마다 끊어서 읽는다.
  • $12\,5000$ → 십이만오천
  • $723\,0000$ → 칠백이십삼만
  • $9\,5000\,0000$ → 구억오천만
• 각 $4$자리 안에서는 일반적인 숫자 읽는 법을 따른다.
  • $1234$ → 천이백삼십사
  • $5\,6789$ → 오만육천칠백팔십구
• 만, 억, 조 단위가 있으면 앞 숫자를 먼저 읽고 단위를 붙인다.
  • $1\,2345\,6789$ → 일억이천삼백사십오만육천칠백팔십구
  • $3\,4500\,0000\,0070$ → 삼조사천오백억칠십
• 십, 백, 천 단위의 $1$은 생략한다.
  • $15$ → 십오
  • $123$ → 백이십삼
  • $1017$ → 천십칠

$1000$은 천, $1\,0000$은 일만으로 읽음에 유의하라.

입력 형식

첫 줄에 두 정수 $N$과 $K$가 공백으로 구분되어 주어진다. ($1 \le K \le N \le 10^{16} - 1$)

출력 형식

첫 줄에 위 규칙을 따라 주년을 붙여 우리말로 읽었을 때 사전 순으로 $K$번째에 오는 수를 출력한다.

예제 1

10 4

10

예제 2

11 5

10

예제 설명

• 예제 1에서 $1$부터 $10$까지 정수를 위 규칙대로 읽으면 차례로 일, 이, 삼, 사, 오, 육, 칠, 팔, 구, 십이고, 사전 순으로 정렬하면 구주년, 사주년, 삼주년, 십주년, 오주년, 육주년, 이주년, 일주년, 칠주년, 팔주년이다. 따라서 이 중 네 번째 단어는 십주년 ($10$)이다.
• 비슷하게, 예제 2에서 $1$부터 $11$까지 정수를 위 규칙대로 읽으면 차례로 일, 이, 삼, 사, 오, 육, 칠, 팔, 구, 십, 십일이고, 사전 순으로 정렬하면 구주년, 사주년, 삼주년, 십일주년, 십주년, 오주년, 육주년, 이주년, 일주년, 칠주년, 팔주년이다. 따라서 이 중 다섯 번째 단어는 십주년 ($10$)이다.

채점 방식

입력 케이스들은 다음과 같은 종류로 구별되며, 한 종류의 케이스를 다 맞혀야 그 종류에 배정된 점수를 받을 수 있다.

해설