Тайпада \(n\) батыр бар және оларды тәжірибесі мен жауынгерлік ерлігі бойынша аз тәжірибелі батырдан ең тәжірибеліге дейінгі тәртіппен \(1\)-ден \(n\)-ге дейінгі сандармен нөмірлеуге болады. Яғни, ең тәжірибесіз батырдың нөмірі \(1\), ал ең тәжірибелі батырдың нөмірі \(n\). Сонымен қатар, олардың әрқайсысының бойы \(a_i\) өлшенеді және олар \(1\)-ден \(n\)-ге дейінгі сандармен беріледі. Әр батыр өзінше ерекше болғандықтан, олардың бойлары да әртүрлі.

Батырлардан жасақ жинауға болады, кейбір батырларды таңдап. Жасақ әрқашан ең тәжірибелі батырдың басшылығымен болады. Ақсақалдың айтуынша, батырлардың жасағы жақсы деп аталады, егер олардың тәжірибесі бойынша реті бойлары бойынша ретімен сәйкес келсе.

Осылайша, \(b_i\) – батыр \(i\) басқаратын ең үлкен жақсы жасақ. Ақсақалдардың ойынша, тайпаның күші \(P([a_1,\ldots,a_n])\) олардың батырларымен анықталады: \[P([a_1,\ldots,a_n]) = b_1 \oplus b_2 \oplus \ldots\oplus b_n\] мұндағы \(\oplus\) – биттік XOR операциясы.

Тайпаның күшін есептеу ақсақал үшін оңай болатын, сондықтан ол сізді сынамақшы: егер олардың бірі қайтып келмесе не болады? Әрбір \(i=1,\ldots,n\) үшін \(i\)-ші батырсыз тайпаның күшін есептеңіз.

Енгізу

Бірінші жолда бір сан \(n\) (\(1 \le n \le 3 \cdot 10^5\)) – тайпадағы батырлардың саны берілген.

Келесі жолда \(n\) сан \(a_1,\ldots,a_n\) (\(1 \le a_i \le n\)) – батырлардың бойлары. \(a_i\) әртүрлі екендігіне кепілдік беріледі.

Шығару

Бір жолда \(n\) сан \(c_1,\ldots, c_n\) шығарыңыз, мұндағы \(c_i\) – \(i\)-ші батырсыз тайпаның күші.

Мысалдар

Енгізу 1

3
2 3 1

Жауап 1

0 0 3

Енгізу 2

7
1 3 2 6 5 4 7

Жауап 2

1 4 4 5 5 5 2