404393: GYM101492 J Deciphering Oracles

China is considered a forefather of math in Asia. Chinese mathematicians developed the binary system, and they had notions of algebra, trigonometry, and geometry. The most ancient records of Chinese math go back to the Shang dynasty (1,600-1,050 BC). Mathematicians at that time recorded their findings in animal bones and turtle plastrons. These texts were known as "Oracle Bones".

The office of the Investigators of Extraordinary Mysteries (IME, in Portuguese) is located in Anyang, capital of the Shang dynasty, and they have with them one of these oracles. The challenge to decipher this oracle was accepted by Marcio "the Indispensable" Himura. Marcio found that the oracle refers to a decimal system a bit different than the one we use. Working out on deciphering the oracle, he found that:

1. The only numbers that are considered are integers from 1 to N.
2. Given two distinct number x = a₁a₂... a_n and y = b₁b₂... b_m, we consider x < y if
   • , or if
   • and x < y (according to the decimal number system).

Marcio was surprised by the last part of the oracle. He concluded that the Chinese had an algorithm that, given a number K, finds the position of K in the number system. Besides, they know how to find the number that occupies position K. Unfortunately, the investigators at IME have not yet found the oracles where such algorithms are described.

Marcio is very curious to know how this can be done. He knows you wish to qualify for the ACM ICPC World Finals next year, and so he challenged you to solve this problem.

The input has two integers, N and K.

• 1 ≤ N < 10¹⁸
• 1 ≤ K ≤ N

The output has two integers separated by a space. The first integer is the position of K in the number system. The second is the number that occurs at position K.

10 2

3 10

100 5

16 11