8. Okázalá svadba

Usáma a Maru sa rozhodli, že spravia tú najokázalejšiu svadbu, akú kedy Trojsten videl. Rozhodli sa preto, že každý hosť dostane ručne šitého motýlika alebo mašľu do vlasov. Výhodou je, že pri objednávaní to netreba rozlišovať, lebo je to vlastne to isté, len inak nazvané. V krajčírskej firme J&P¹ si teda objednali zákazku na \(n\) motýlikov.

Jano je veľký motýlikový umelec a na tejto zákazke sa vybláznil, preto je každý motýlik iný a originálny. Ako však vieme, nie každý originálny nápad dopadne úspešne a teda nie všetky motýliky vyzerajú rovnako dobre. Každému motýliku preto Usáma a Maru priradili číslo zodpovedajúce jeho kráse.

Situácia sa však skomplikovala. Nie sú si totiž istí, koľko pozvaných hostí naozaj príde. Chceli sa preto s Janom dohodnúť, že keď zistia počet hostí \(k\), ktorí prídu na svadbu, zoberú si \(k\) najkrajších motýlikov. To im však Jano zakázal, zoradil motýliky podľa poradia ušitia a povedal, že si budú môcť vybrať iba súvislý úsek dĺžky \(k\).

V tom okamihu sa rozpútala hádka². Usáma chcel, ako správny egoista, získať najkrajší motýlik pre seba a chcel preto úsek s čo najväčším maximom krásy. Maru je ale štedrá osoba a páči sa jej rozmanitosť, preto chcela maximalizovať bitový OR krás všetkých motýlikov, ktoré budú vo vybranom úseku.

Nakoniec sa dohodli sa dohodli na kompromise³ a rozhodli sa maximalizovať súčet maximálneho prvku a bitového ORu všetkých krás v úseku. Stále však nevedia, koľko hostí príde na svadbu, preto by chceli vedieť dopredu, ktorý úsek vybrať pre všetky možné \(k\).

Úloha

Na vstupe dostanete postupnosť kladných celých čísiel dĺžky \(n\). Vašou úlohou bude pre každé \(k\) od \(1\) po \(n\) nájsť taký súvislý úsek dĺžky \(k\) v tejto postupnosti, že súčet maxima v tomto úseku a bitového ORu prvkov tohoto úseku je najväčší možný.

Formát vstupu

Na prvom riadku sa nachádza číslo \(n\) (\(1 \leq n \leq 100\,000\)), ktoré označuje počet vyrobených motýlikov. Nasleduje \(n\) čísel, ktoré predstavujú krásy jednotlivých motýlikov v poradí, v akom boli vytvorené. Krásy motýlikov sú kladné celé čísla neprevyššujúce \(10^9\).

Formát výstupu

Vypíšte \(n\) čísel na samostatné riadky, kde \(k\)-te z nich predstavuje najväčší možný súčet požadovaných vlastností pre úseky dĺžky \(k\).

Príklad

Input:

3
1 0 2

Output:

4
4
5