문제

울트라 369 게임은 1부터 100까지의 수를 정해진 규칙에 따라 순서대로 말하는 게임이다. 100까지 세고 나면 다시 1로 돌아가 같은 과정을 무한히 반복한다. 게임의 상세 규칙은 다음과 같다.

• 수를 1부터 100까지 차례대로 센다. 100 다음에는 다시 1이 온다.
• 수의 십진수 표기에 3, 6, 9 중 하나라도 포함되어 있다면, 수를 읽는 대신 '짝'을 한 번 말한다.
• 숫자 3, 6, 9가 포함되지 않은 수는 한국어 고유어 수사로 읽는다. 이때 한 음절을 한 턴으로 간주하여 한 턴에 한 음절씩 말한다.

수를 고유어 수사로 읽는 규칙은 다음과 같다.

• 한 자리 수: 1(하나), 2(둘), 3(셋), 4(넷), 5(다섯), 6(여섯), 7(일곱), 8(여덟), 9(아홉)
• 십 단위 수: 10(열), 20(스물), 30(서른), 40(마흔), 50(쉰), 60(예순), 70(일흔), 80(여든), 90(아흔)
• 두 자리 수: 십의 자리 수사 뒤에 일의 자리 수사를 이어 붙여서 읽는다. 예를 들어, 14는 '열넷', 28은 '스물여덟', 57은 '쉰일곱'이다.
• 백: 100은 '백'으로 읽는다.

음절 분리의 예시는 다음과 같다.

• 1: '하나'이므로 두 턴에 걸쳐 ['하', '나']를 말한다.
• 12: '열둘'이므로 두 턴에 걸쳐 ['열', '둘']을 말한다.
• 21: '스물하나'이므로 네 턴에 걸쳐 ['스', '물', '하', '나']를 말한다.
• 13: 3이 포함되어 있으므로 한 턴에 '짝'을 말한다.

처음 몇 개의 수에 따른 게임의 진행은 다음과 같다.

• 수 1: ['하', '나'] (1~2번째 턴)
• 수 2: ['둘'] (3번째 턴)
• 수 3: ['짝'] (4번째 턴)
• 수 4: ['넷'] (5번째 턴)
• 수 5: ['다', '섯'] (6~7번째 턴)
• 수 6: ['짝'] (8번째 턴)
• 수 7: ['일', '곱'] (9~10번째 턴)
• 수 8: ['여', '덟'] (11~12번째 턴)
• 수 9: ['짝'] (13번째 턴)
• 수 10:['열'] (14번째 턴)

따라서 1번째 턴은 하, 4번째 턴은 짝, 6번째 턴은 다가 된다. 100까지의 주기가 끝나면 다시 1부터 시작하여 동일한 음절들이 반복된다.

게임이 무한히 반복될 때, $N$번째 턴에 말해야 하는 음절을 구하여라.

입력

첫째 줄에 정수 $N$ ($1 \le N \le 10^{18}$)이 주어진다.

출력

$N$번째 턴에 말해야 하는 음절을 출력한다. 만약 박수를 쳐야 하는 턴이라면 '짝'을 출력한다.

예제 입력 1

6

예제 출력 1

다

노트

본 문제는 한글 음절을 판별하고 출력해야 하므로, 실행 환경의 인코딩 설정에 따라 출력 오류가 발생할 수 있습니다. 한글 처리가 직관적인 Python의 사용을 권장합니다.

Python (권장) 터미널 환경에 따른 출력 깨짐을 방지하기 위해 스트림 인코딩을 UTF-8로 지정합니다.

import sys, io
if sys.stdout.encoding != 'utf-8':
    sys.stdout = io.TextIOWrapper(sys.stdout.detach(), encoding='utf-8')

Java 표준 출력을 UTF-8 인코딩 스트림으로 직접 감싸서 출력합니다.

BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out, StandardCharsets.UTF_8));

C, C++ UTF-8 환경에서 한글은 일반적으로 한 글자당 3바이트를 차지합니다. 한 음절씩 분리하여 처리하고 싶다면 바이트 길이를 판별하는 로직이 필요합니다.

// 한글(3바이트)과 영문/숫자(1바이트)를 판별하여 분리
for (int i = 0; i < res.length(); ) {
    int len = ((res[i] & 0xf0) == 0xe0) ? 3 : 1;
    result.push_back(res.substr(i, len));
    i += len;
}