Muallif: shoyim

G. Beshtosh o'yini

Vaqt limiti: 1000 ms Xotira limiti: 128 mb

Qishloq bolalari orasida mashhur bo'lgan "Beshtosh" o'yinining bir varianti bor: yerga \(n\) ta g'uj-g'uj tosh uyumlari qo'yiladi, \(i\)-uyumda \(a_i\) dona tosh bo'ladi. Ikki o'yinchi — Anvar va Botir — navbat bilan yurish qiladi. Anvar birinchi bo'lib boshlaydi.

Har bir yurishda o'yinchi istalgan bitta uyumni tanlaydi va o'sha uyumdan kamida bitta, istagancha ko'p toshni olib tashlaydi (butun uyumni ham olib tashlash mumkin). Navbatida yura olmagan o'yinchi (ya'ni barcha uyumlar bo'sh bo'lib qolganda yurish kerak bo'lgan o'yinchi) yutqazadi.

Ikkala o'yinchi ham eng aqlli (optimal) tarzda o'ynaydi. Shu holatda kim g'olib chiqadi?

Nega bu qiziq?

Qarasangiz, uyumlar soni va toshlar joylashuvi juda xilma-xil bo'lishi mumkin — lekin g'alaba faqat bitta oddiy amalga bog'liq ekan: barcha \(a_i\) larning \(\text{XOR}\) (\(\oplus\)) yig'indisi! Agar bu yig'indi \(0\) bo'lsa, boshlovchi (Anvar) qancha urinmasin albatta yutqazadi. Aks holda, u albatta g'olib strategiyasini topa oladi. Bu o'yinlar nazariyasining eng mashhur va "sehrli" natijalaridan biri.

Kiruvchi ma'lumotlar

Birinchi qatorda bitta son \(t\) (\(1 \le t \le 10^4\)) — sinovlar soni beriladi.

Har bir sinov uchun:

• Birinchi qatorda \(n\) (\(1 \le n \le 10^5\)) — tosh uyumlari soni;
• Ikkinchi qatorda \(n\) ta butun son \(a_1, \dots, a_n\) (\(0 \le a_i \le 10^9\)) — har bir uyumdagi toshlar soni.

Barcha sinovlardagi \(n\) larning yig'indisi \(2 \times 10^5\) dan oshmaydi.

Chiquvchi ma'lumotlar

Har bir sinov uchun — kim g'olib bo'lishini chop eting: Anvar yoki Botir.

Misollar

1

2
3
1 2 3
2
3 4

Botir
Anvar

2

1
1
0

Botir

3

1
1
5

Anvar

Izoh

1-test:

• \([1, 2, 3]\): \(1 \oplus 2 \oplus 3 = 0\) \( \to\) boshlovchi (Anvar) yutqazadi \( \to\) Botir.
• \([3, 4]\): \(3 \oplus 4 = 7 \neq 0\) \( \to\) Anvar \(4 \to 3\) qiladi, \([3, 3]\) hosil bo'ladi, so'ng oyna strategiyasi bilan g'olib chiqadi \( \to\) Anvar.

2-test:
\([0]\) — tosh yo'q, Anvar yura olmaydi, zudlik bilan yutqazadi \(\to\) Botir.

3-test:
\([5]\) — ​​​​​​​\(5 \neq 0\), Anvar hammasini bir yurishda oladi, Botirga yurish qolmaydi \(\to\) Anvar.

Qoida: ​​​​​​​\(\text{XOR} = 0\) \(\to\) boshlovchi yutqazadi; \(\text{XOR} \ne0\) \(\to\) boshlovchi yutadi.