Universal Cup Judging System

Universal Cup

시간 제한: 1.0 s 메모리 제한: 512 MB 총점: 100 해킹 가능 ✓
통계

Noir memiliki $n$ permata. Permata ke-$i$ memiliki sebuah bilangan bulat positif $a_i$ yang tertulis di atasnya. Noir ingin membagi permata-permata ini ke dalam beberapa kelompok tak kosong. Setiap permata termasuk ke dalam tepat satu kelompok.

Misalkan kelompok ke-$i$ berisi permata dengan label $k_{i,1}, k_{i,2}, \dots, k_{i,p}$, maka Noir menganggap kecerahan dari kelompok ke-$i$ sebagai $a_{k_{i,1}} \oplus a_{k_{i,2}} \oplus \cdots \oplus a_{k_{i,p}}$, dengan $\oplus$ adalah operasi bitwise-XOR. Nyatakan kecerahan dari kelompok ke-$i$ sebagai $B_i$.

Untuk suatu metode pengelompokan yang terdiri dari $m$ kelompok, Noir menganggap nilai dari metode ini sebagai $B_1 \& B_2 \& \dots \& B_m$, dengan $\&$ adalah operasi bitwise-AND.

Noir ingin mencari nilai maksimum yang mungkin di antara semua metode pengelompokan.

Masukan

Masukan terdiri atas beberapa kasus uji. Baris pertama masukan berisi sebuah bilangan bulat $T$ ($1 \le T \le 10^4$), yaitu banyaknya kasus uji.

Untuk setiap kasus uji, baris pertama berisi sebuah bilangan bulat $n$ ($1 \le n \le 5 \times 10^5$), yaitu banyaknya permata.

Baris kedua berisi $n$ bilangan bulat $a_1, a_2, \cdots, a_n$ ($1 \le a_i < 2^{60}$), yaitu bilangan bulat yang tertulis pada permata.

Dijamin bahwa jumlah $n$ di seluruh kasus uji tidak melebihi $5 \times 10^5$.

Keluaran

Untuk setiap kasus uji, cetak sebuah bilangan bulat yang menyatakan nilai maksimum yang mungkin di antara semua metode pengelompokan.

Contoh

4
4
1 2 3 1
6
4 7 5 2 6 3
4
14 15 9 18
2
251508091405 13011908091815
2
6
26
13121614001578

Catatan

Untuk kasus uji pertama, salah satu metode pengelompokan yang mungkin adalah $[1, 2, 3, 1] = [1, 3], [2, 1]$ dengan nilai $B_1 \& B_2 = (1 \oplus 3) \& (2 \oplus 1) = 2 \& 3 = 2$. Metode pengelompokan lain yang mungkin adalah $[1, 2, 3, 1] = [1, 2, 3, 1]$, dengan nilai yang lebih rendah yaitu $B_1 = 1 \oplus 2 \oplus 3 \oplus 1 = 1$. Dapat dibuktikan bahwa tidak mungkin mencapai nilai yang lebih besar dari $2$.

Untuk kasus uji kedua, metode pengelompokan terbaik adalah $[4, 7, 5, 2, 6, 3] = [7], [5, 3], [6], [4, 2]$ dengan nilai $7 \& (5 \oplus 3) \& 6 \& (4 \oplus 2) = 6$.

Discussions

About Discussions

The discussion section is only for posting: General Discussions (problem-solving strategies, alternative approaches), and Off-topic conversations.

This is NOT for reporting issues! If you want to report bugs or errors, please use the Issues section below.

Open Discussions 0
No discussions in this category.

Issues

About Issues

If you find any issues with the problem (statement, scoring, time/memory limits, test cases, etc.), you may submit an issue here. A problem moderator will review your issue.

Guidelines:

  1. This is not a place to publish discussions, editorials, or requests to debug your code. Issues are only visible to you and problem moderators.
  2. Do not submit duplicated issues.
  3. Issues must be filed in English or Chinese only.
Active Issues 0
No issues in this category.
Closed/Resolved Issues 0
No issues in this category.