Задача A + B#1758
QQ та OO завжди грають у гру A + B. QQ дає два десяткових числа A і B, а OO миттєво відповідає їхньою сумою. Однак виконувати одне й те ж надто довго стає нудно. Тож сьогодні вони завершують цю просту гру та вводять нові правила.
Правило 1: При додаванні A та B використовуються їхні двійкові подання.
Правило 2: Можна накладати однаковий суфікс A на префікс B.
Правило 3: Якщо двійкове подання B є підрядком у A, можна використати A для накладання на B.
Щоб зробити задачу цікавішою, QQ дає чисел. OO має використати кожне число рівно один раз і знайти найменшу можливу суму. OO немає часу думати і просить вас про допомогу.
Декілька тестів. Кожен тест починається з числа , далі йде (0 < n < 16) рядків, у кожному з яких записане десяткове число a_i (0 < a_i < 2^{64}), як описано вище. Опрацьовуйте вхід до кінця файлу.
Для кожного тесту виведіть найменшу можливу відповідь у окремому рядку. Якщо відповідь велика, виведіть її за модулем .
Приклад 1