Məsələ A + B#1758
QQ və OO həmişə A + B oyununu oynayırlar. QQ iki onluq ədəd — A və B verir, OO isə onların cəmini dərhal cavablandırır. Ancaq uzun müddət eyni şeyi etmək darıxdırıcadır. Ona görə də bu gün, onlar asan oyunu bitirib yeni qaydalar təqdim edirlər.
Qayda 1: A və B-ni topladıqda, onların ikilik yazılışlarından istifadə edirik.
Qayda 2: A-nın sonluğu ilə B-nin başlanğıcını üst-üstə gətirə bilərik.
Qayda 3: Əgər B-nin ikilik yazılışı A-nın alt sətri olarsa, A-nı istifadə edərək B-ni üst-üstə gətirə bilərik.
Məsələni daha maraqlı etmək üçün QQ n ədəd verir. OO hər bir ədədi dəqiq bir dəfə istifadə etməlidir və mümkün olan ən kiçik cəmi tapmalıdır. OO-nun düşünməyə vaxtı yoxdur və sizdən yardım istəyir.
Bir neçə test var. Hər test əvvəlcə bir n ədədi ilə başlayır, onu isə ardıcıl n (0 < n < 16) sətir izləyir. Hər sətirdə yuxarıda təsvir olunan bir onluq ədəd a_i (0 < a_i < 2^{64}) verilir. Girişi faylın sonuna qədər oxuyun.
Hər test üçün ən kiçik mümkün cavabı ayrıca sətirdə çap edin. Əgər cavab böyükdürsə, onu 1000000009-a görə çap edin.
Nümunə 1