Qarışmış göstəricilər#13073

Qarışmış göstəricilər

3 saniyə
256 meqabayt

Qoca alximik Orest sehrli kristaldan ibarət kolleksiya saxlayır; -ci kristalın müsbət tam yükü a_i-dir. Müxtəlif kristalların yükləri üst-üstə düşə bilər.

Orestin iki cihazı var. Əgər boş olmayan kristal qrupunu tərəziyə qoysanız, o, qrupun ümumi yükünü, yəni yüklərin cəmini göstərəcək. Əgər eyni qrupu rezonatora qoysanız, o, onların yüklərinin bitlər üzrə VƏ YA (OR) nəticəsini göstərəcək.

Bir gecə Orest 2^n - 1 boş olmayan kristal qrupunun hər birini hər iki cihazda ölçdü və bütün göstəriciləri jurnala yazdı. Beləliklə, jurnalda dəqiq olaraq 2 \cdot (2^n - 1) ədəd var. Təəssüf ki, qeydlər ayrı-ayrı vərəqlərdə idi və onlar qarışdı: indi hər bir göstəricinin hansı qrupa aid olduğu və onu hansı cihazın verdiyi bilinmir. Kristalların özləri isə artıq satılıb.

İxtiyari sırada verilmiş 2 \cdot (2^n - 1) göstəriciyə əsasən kristalların yüklərini bərpa edin.

Formal olaraq, a_1, a_2, \ldots, a_n massivi və boş olmayan S \subseteq \{1, \ldots, n\} indekslər çoxluğu üçün \mathrm{sum}(S) = \sum_{i \in S} a_i və \mathrm{or}(S) = a_{i_1} \mathbin{|} a_{i_2} \mathbin{|} \ldots \mathbin{|} a_{i_k} işarə edək, burada S = \{i_1, \ldots, i_k\}, isə bitlər üzrə VƏ YA əməliyyatıdır. Jurnal — bütün 2^n - 1 boş olmayan çoxluqları üçün və ədədlərindən ibarət multiçoxluqdur (əgər \mathrm{sum}(S) = \mathrm{or}(S) olarsa, bu üçün həmin qiymət iki dəfə daxil olur).

Giriş

Birinci sətirdə bir tam ədəd (1 \le t \le 10^5) — test hallarının sayı verilir.

Hər test halı iki sətirdən ibarətdir. Birinci sətirdə tam ədədi (1 \le n \le 20) — kristalların sayı verilir. İkinci sətirdə 2 \cdot (2^n - 1) tam ədəd b_1, b_2, \ldots, b_{2 (2^n - 1)} (1 \le b_j \le 2 \cdot 10^{10}) — jurnaldakı göstəricilər ixtiyari sırada verilir.

Zəmanət verilir ki, hər test halının göstəriciləri 1 \le a_i \le 10^9 şərtini ödəyən hansısa tam ədəddən ibarət a_1, \ldots, a_n massivinin dəqiq jurnalıdır.

Bütün test halları üzrə 2^n cəmi 2^{20}-ni aşmır.

Çıxış

Hər test halı üçün ayrıca sətirdə tam ədədi a_1, a_2, \ldots, a_n (1 \le a_i \le 10^9) ixtiyari sırada elə çıxarın ki, bu massivin jurnalı multiçoxluq kimi verilmiş göstəricilərlə üst-üstə düşsün. Bir neçə cavab varsa, onlardan istənilən birini çıxarın.

Nümunələr

Nümunə 1

Loading
Loading

Qeyd

Birinci test halında yeganə kristalın yükü -dir: hər iki cihaz göstərir.

İkinci test halında yüklər və -dir: tərəzi , , , rezonator isə , , göstərir.

Üçüncü test halında hər iki kristalın yükü -dir: tərəzi , , , rezonator isə , , göstərir.

Dördüncü test halında yüklər , , -dır. Tərəzi , , , , , , , rezonator isə , , , , , , göstərir.