D. 2 олонлог

хугацааны хязгаарлалт 2 секунд

санах ойн хязгаарлалт 256 мегабайт

оролт стандарт оролт

гаралт стандарт гаралт

Бяцхан Петя тоонуудад маш их дуртай. Саяхан түүний ээж $n$ ширхэг сөрөг биш бүхэл тоонуудын цуглуулгыг түүнд бэлэглэжээ. Мөн Петя-д тоонуудаас ч илүү дуртай цорын ганц зүйл байдаг ба энэ нь Маша-тай тоглох юм. Тэрээр шуудхан л өөрийн шинэ цуглуулгын зарим хэсгийг түүнд өгөхөөр шийджээ. Тоглоомыг илүү сонирхолтой болгохын тулд Петя дараах нөхцөлүүдийг хангах тоонуудын цуглуулгыг Маша-д өгөхөөр шийджээ:

  • Петя-д үлдсэн бүх тоонуудын $xor$ үйлдлийн утгыг $x_{1}$-ээр, Маша-д өгсөн бүх тоонуудын $xor$ үйлдлийн утгыг $x_{2}$-оор тэмдэглэе. Тэгвэл $(x_{1} + x_{2})$-ын утга нь аль болох их байх ёстой.
  • Хэрэв өмнөх нөхцөлийг хангаж байхаар цуглуулгыг хуваах олон тооны арга байвал Петя $x_{1}$ утгыг хамгийн бага байлгах юм.

$xor$ үйлдэл гэдэг нь битийн "$OR$" үйлдлийн үгүйсгэл ба Паскал хэлэнд "$xor$" гэж тэмдэглэх ба C/C++/Java хэлэнд "$^$" гэж тэмдэглэнэ.

Петя-д туслан дээр дүрслэгдсэнээр цуглуулгыг хувааж өгнө үү. Хэрэв олон тооны тохиромжтой хуваах аргууд байвал тэдгээрийн алийг нь ч олсон болно. Петя Маша-д өөрийн тоонуудаас хэсэг тоог өгснийхөө дараа ямар ч тоогүй үлдэж болохыг анхаарна уу. Мөн Петя Маша-д юу ч өгөхгүй байхад эсрэг нөхцөл байдал нь боломжтой байх юм. Аль ч тохиолдолд бид тоонуудын хоосон олонлогийн $xor$ үйлдлийн утга нь 0-тэй тэнцүү гэж үзнэ.

Оролт

Эхний мөрөнд Петя-ын ээж түүнд бэлэглэсэн тоонуудын тоо болох бүхэл тоо $n$ ($1 ≤ n ≤ 10^{5}$) өгөгдөнө. 2-дахь мөрөнд зайгаар тусгаарлагдсан бүхэл тоонууд өгөгдөх ба тэдгээр нь сөрөг биш бөгөөд $10^{18}$-аас хэтрэхгүй байна.

Гаралт

Зайгаа тусгаарлагдсан $n$ ширхэг бүхэл тоо хэвлэх ба тэдгээрийн $i$-дахь нь хэрэв Петя $i$-дахь тоог өөртөө үлдээсэн бол 1 гэсэн утгатай байх бөгөөд хэрэв Петя $i$-дахь тоог Маша-д өгсөн бол 2 гэсэн утгатай байна. Тоонууд нь оролтод өгөгдсөн дарааллаараа дугаарлагдсан байна.

Орчуулсан: Баатархүү

Жишээ тэстүүд

Оролт
6
1 2 3 4 5 6
Гаралт
2 2 2 2 2 2
Оролт
3
1000000000000 1000000000000 1000000000000
Гаралт
2 2 2
Оролт
8
1 1 2 2 3 3 4 4
Гаралт
1 2 1 2 2 2 1 2
Сэтгэгдлүүдийг ачааллаж байна...