Вот уже несколько месяцев Капитан Флинт и его матросы держат курс к диким берегам Байтляндии, вечерами вдоволь напиваясь ромом и болтая о том о сём. В такие моменты дядя Богдан часто вспоминает своего одаренного племянника Дениса. Сегодня он поведал историю о том, как мальчик помог придумать очень интересную задачу, и предложил команде справиться с ней.
Сначала, Дядя Богдан записал на доске целое положительное десятичное число \(x\) длины \(n\). Потом, немного подумав, стер \(x\) и написал число \(k\), образованное путем конкатенации двоичных записей цифр числа \(x\) (без ведущих нулей). Например, пусть \(x = 729\), тогда \(k = 111101001\) (так как \(7 = 111\), \(2 = 10\), \(9 = 1001\)).
Через некоторое время дядя Богдан понял, что не знает, что делать с \(k\) дальше и позвал на помощь Дениса. Денис, недолго думая, стер последние \(n\) цифр числа \(k\) и назвал полученное число \(r\).
В результате, Денис предложил искать такое число \(x\) длины \(n\), что полученное \(r\) (как число) максимально возможное. Если же подходящих \(x\) несколько, то Дениса интересует только минимальное из них.
Все члены команды, в том числе капитан Флинт, успешно справились с задачей. Все, кроме юного матроса Кости, который перебрал с выпивкой и был уже не в том состоянии. А Вы в состоянии сегодня решить эту задачу?
Уточнение: в данной задаче, мы сравниваем числа (\(x\) или \(k\)) как числа (независимо от того, в какой системе счисления они записаны), поэтому \(729 < 1999\) или \(111 < 1000\).
Примечание
Во втором наборе входных данных (с \(n = 3\)), если дядя Богдан записал \(x = 998\), то \(k = 100110011000\). Денис же (удалением последних \(n = 3\) цифр) получит \(r = 100110011\).
Можно доказать, что \(100110011\) — максимально возможное число \(r\), которое может получить Денис, и \(998\) — минимальный \(x\), из которого его можно получить.