Masala #0207

Xotira 32 MB Vaqt 1000 ms
14

To’plam & X

Sizga \(n\) ta elementdan iborat \(A(A_1, A_2, \dots, A_n)\) to’plam berilgan.

\(F(x) = \displaystyle\sum_{i=1}^n A_i ∧ x\)

Bu yerda \(F(x)\) funksiya \(A\) to’plamning barcha elementlari bilan \(x\) orasida bitwise and operatorini qo’llab hosil bo’lgan qiymatlarning umumiy summasini hisoblab beradi.

Sizning vazifangiz \(F(x)\) funksiyadan qaytadigan qiymat eng katta bo’ladigan, ikkilik ifodalanishida jami \(L\) ta 1 ishtirok etadigan \(x\) lar sonini topishdan iborat!


Kiruvchi ma'lumotlar:

Kirish faylining dastlabki satrida bitta butun son, \(T \space (1 \le T \le 1000)\) testlar soni kiritiladi. Keyingi qatordan boshlab har bir test uchun alohida ikkita qatorning birinchi satrida ikkita butun son, \(n \space (1 \le N \le 20000)\) va \(L \space (1 \le L \le 30)\), mos ravishda \(A\) to’plam elementlar soni va \(x\) ning ikkilik ko’rinishidagi 1 lar soni, ikkinchi satrida esa \(n\) ta butun son, \(A (1 \le A_i \le 10^9)\) to’plam elementlari kiritiladi.

Barcha testlardagi \(N\) lar yig’indisi 200000 dan oshmasligi kafolatlanadi.


Chiquvchi ma'lumotlar:

Har bir test uchun alohida qatorda \(F(x)\) funksiyasidan eng katta qiymat qaytaradigan \(x\) ning bo’lishi mumkin bo’lgan qiymatlar sonini chop eting, agar bunday sonlar cheksiz bo’lsa o’rniga -1 chop eting.


Misollar
# input.txt output.txt
1
2
5 2
3 5 7 1 4
5 1
3 5 7 1 4
2
1