Задачи
Задача из старого ЕГЭ
Задача из старого ЕГЭ
Строки (цепочки цифр) строятся по следующему правилу.
Первая строка состоит из одного символа - цифры "\textbf{1}". Каждая из последующих цепочек создаётся такими действиями: в очередную строку записывается сначала номер строки (без ведущих нулей), а затем два раза приписывается предыдущая строка.
Вот первые \textbf{4} строки, созданные по этому правилу:
\begin{enumerate}
\item \textbf{1}
\item \textbf{211}
\item \textbf{3211211}
\item \textbf{432112113211211}
\end{enumerate}
А, например, \textbf{11}-я строка будет начинаться так:
11. \textbf{1110987}...
По заданным \textbf{N} и \textbf{K} определите, какая цифра будет стоять в \textbf{N}-ой строке на \textbf{K}-ом месте, либо что длина строки меньше \textbf{K}.
\InputFile
Вводятся два натуральных числа \textbf{N} и \textbf{K} (\textbf{1} ≤ \textbf{N} ≤ \textbf{100000}, \textbf{1} ≤ \textbf{K} ≤ \textbf{10^15}).
\OutputFile
Определите, какая цифра будет стоять в \textbf{N}-ой строке на \textbf{K}-ом месте и выведите её. Если длина \textbf{N}-ой строки меньше \textbf{K}, выведите \textbf{-1} (минус один).
Входные данные #1
3 2
Выходные данные #1
2