404393: GYM101492 J Deciphering Oracles

Memory Limit:512 MB Time Limit:1 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

J. Deciphering Oraclestime limit per test1 secondmemory limit per test512 megabytesinputstandard inputoutputstandard output

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 = a1a2... an and y = b1b2... bm, 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.

Input

The input has two integers, N and K.

  • 1 ≤ N < 1018
  • 1 ≤ K ≤ N
Output

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.

ExamplesInput
10 2
Output
3 10
Input
100 5
Output
16 11

Source/Category

加入题单

上一题 下一题 算法标签: