Xəzinələr adasında dəniz quldurlarının yeraltı mağarası aşağıdakı prinsiplər əsasında qazılmışdı. Gizli girişdən sonra sağa və sola iki tunel çıxışı olan mağara yerləşir. Hər tunel yenə iki tuneli olan mağara ilə qurtarır və s. Hər tunelin uzunluğu vahidə bərabərdir. Girişdən \textbf{D} məsafədə olan sonuncu mağara daha çıxışa malik deyil. Tunellərin heç biri öz aralarında kəsişmir və eyni mağaraya aparmır. \textbf{D} ədədi yeraltı mağaranın dərinliyi adlanır. \includegraphics{https://static.e-olymp.com/content/63/6313dea2edd831a77597fd17a1dbf9b306f04a6b.jpg} Hər bir sonuncu mağarada xəzinə olan bir sandıq gizlədilmişdir. Kapitan Cek Vorobun adaya gəlişindən əvvəl dəniz quldurları bu sandıqların yerini Kapitanının sonuncu göstərişinə uyğun olaraq dəyişməyi qərara aldılar. Quldurlar yeraltı mağaranın planını çəkdilər və sonuncu mağaraları soldan sağa nömrələdilər. Sonra hər bir xəzinənin Kapitanın gəlişindən əvvəl olacağı mağaraya nömrə təyin edildi. Yerdəyişmədən sonra hər bir mağarada yenidən yalnız bir sandıq oldu. Xəzinənin təhlükəsizliyini təmin etmək üçün quldurlar yalnız iki mağara sandıqları arasında dəyişmə apara bilərlər. Yalnız bir yerdəyişmə aparıldıqdan sonra digərinə başlamaq olar. Sandıqları tələb olunan şəkildə yerləşdirmək üçün quldurlara sandıqları daşımağa zəruri olan ən kiçik ümumi məsafəni tapmaq lazımdır. \InputFile Hər bir testdə birinci sətirdə bir tam\textbf{ D} (\textbf{D} ≤ \textbf{8}) ədədi - yeraltı mağaranın dərinliyi yerləşir. İkinci sətirdə \textbf{2^D} sayda \textbf{1}-dən \textbf{2^D}-dək tam ədədlər verilir. Onlardan hər biri əvvəlcə \textbf{i}-ci mağarada yerləşən sandığın gələcəyi mağaranın nömrəsinin identifikasiyasıdır. \OutputFile Çıxış faylının birinci sətrində yeganə tam ədəd - quldurların xəzinə ilə gedəcəkləri ən kiçik ümumi məsafə yerləşir. İkinci sətirdə yerdəyişmələrin sayına uyğun \textbf{K} tam ədədi verilir.\textbf{ }Each of the next K lines contains two numbers, the cave numbers between which the exchange takes place. The exchanges must be printed in the order they occur.