4의 배수 접두사 수열

시간 제한1초메모리 제한128 MB

요약

N마다 N으로 시작하는 가장 작은 4의 배수를 이어붙인 무한 문자열에서 최대 10^15번째 자리 숫자를 구하는 문제입니다.

문제

양의 정수 N에 대해 A[N]을 다음과 같이 정의한다. A[N]은 십진수 표기가 N으로 시작하는 양의 정수 중 가장 작은 4의 배수이다.

A[1], A[2], A[3], ...을 순서대로 이어 붙이면 무한한 문자열 S가 된다. 이 수열은 12, 20, 32, 4, 52, 60, ...으로 시작하므로 S는 12203245260...으로 시작한다.

양의 정수 K가 주어질 때, S의 K번째 숫자를 구하라.

입력은 여러 테스트 케이스로 이루어진다. 각 테스트 케이스는 한 줄에 하나의 양의 정수 K로 주어진다.

K ≤ 10^15이다. 마지막 줄에는 0이 하나 주어지며, 이 값은 처리하지 않는다.

각 테스트 케이스마다 S의 K번째 숫자를 한 줄에 하나씩 출력한다.