Northern Subregional Contest 2008 - LCA на полном бинарном дереве

Задача A. LCA на полном бинарном дереве ≡

задачи
видимые пробелы
простые формулы
широкий текст
редактор

Автор:	И. Туфанов	Ограничение времени:	2 сек
Входной файл:	input.txt	Ограничение памяти:	64 Мб
Выходной файл:	output.txt

Условие

Дано бесконечное полное бинарное дерево. Его вершины пронумерованы следующим образом: корень имеет номер 1, для каждой вершина с номером n ее левый ребенок имеет номер 2 * n + 1, а правый 2 * n.

Две вершины заданы своими номерами. Найдите номер их наименьшего общего предка, то есть располженного дальше от корня.

Формат входного файла

Во входном файле содержится два числа: номера заданных вершин.

Формат выходного файла

В выходном файле должно содержаться единственное число: номер вершины, являющейся LCA двух заданных.

Ограничения

1 ≤ N ≤ 2³¹ − 1

Примеры тестов

№	Входной файл (`input.txt`)	Выходной файл (`output.txt`)
1	`12 7`	`3`