5. Obiehanie

Pred pár týždňami sa uskutočnilo školské kolo súťaže Zenit v programovaní a mnohí z vás sa ho pravdepodobne zúčastnili. Mohli ste si na ňom všimnúť, že po odovzdaní úlohy ste museli chvíľku počkať na jej vyhodnotenie. Takú malú, 20-minútovú chvíľku. Táto chvíľka vznikla preto, lebo testovač dostal úžasný nápad, ako robiť vyhodnocovanie odovzdaných riešení. Testovať riešenia v tom poradí, v akom prišli sa mu zazdalo príliš trápne a určite neoptimálne, preto sa rozhodol usporiadať turnaje.

Ako to funguje? Najprv treba počkať, kým riešitelia odovzdajú dosť veľa riešení. Každému riešeniu je potom pridelená jeho úžasnosť¹. Následne sa riešenia zoradia vedľa seba v takom poradí, v akom prišli a začne sa turnaj. Ide o klasického turnajového pavúka – najprv súperí prvé riešenie s druhým, potom tretie zo štvrtým a tak ďalej. To úžasnejšie z dvojice riešení vyhrá a postupuje do ďalšieho kola. V druhom kole súperia už len víťazi predchádzajúceho kola rovnakým spôsobom. Takto to pokračuje, až kým nezostane len to úplne najúžasnejšie riešenie, ktoré sa naozaj aj otestuje.

Zenitu sa zúčastnil aj Romanko. Porozhliadal sa okolo seba a už na prvý pohľad vedel, ako úžasné riešenia vyprodukujú ostatní riešitelia. Dokonca aj presne vedel, kedy tieto riešenia pošlú na otestovanie a teda ako budú usporiadané počas turnaja. Romanko by teraz chcel odovzdať svoje riešenie a mať ho aj v rozumnom čase² otestované. Jeho riešenie ale určite nie je dosť úžasné na to, aby mohlo vyhrať turnaj.

Romanko ale vie, že testovač je mysteriózna entita a dá sa rôzne ovplyvňovať. Ak mu človek správne obetuje horalku³, je možné, že jeho riešenie prejde do ďalšieho kola aj keď nebolo to úžasnejšie. Romanko sa teraz potrebuje vopchať medzi ostatné riešenia (napríklad odovzdá čo najskôr a bude teda v turnaji ako prvý) a rád by vedel, koľko horaliek bude musieť obetovať, ak chce vyhrať turnaj a začína na danej pozícií. Môžete mu s tým pomôcť?

Úloha

Na vstupe sú dané úžasnosti \(n-1\) riešení ostatných riešiteľov v takom poradí, v akom budú na testovači. Taktiež je zadaná úžasnosť Romankovho riešenia. Pre každú pozíciu, na ktorú sa môže Romanko vopchať chceme zrátať, koľko horaliek musí obetovať, aby jeho riešenie vyhralo turnaj a bolo teda otestované najskôr.

Formát vstupu

Na prvom riadku sa nachádza číslo \(n\) – počet riešení a \(k\) – úžasnosť Romankovho riešenia. V druhom riadku sa nachádza \(n-1\) rôznych celých čísiel \(a_1 \dots a_{n-1}\) – úžasnosti riešení ostatných riešiteľov. Platí \(1 \leq n, k, a_i \leq 2^{20} = 1\,048\,576\) a že \(n\) je mocninou \(2\). Taktiež platí, že úžasnosti riešení (aj Romanovho) sú navzájom rôzne.

Formát výstupu

Vypíšte \(n\) medzerou oddelených čísiel, pričom \(i\)-te číslo udáva počet horaliek, ktoré Romanko potrebuje obetovať, ak by jeho riešenie začínalo na \(i\)-tej pozícií.

Príklad

Input:

4 2
1 3 4

Output:

1 1 2 2

V tomto príklade Romanko potrebuje obetovať pre prvé a druhé miesto \(1\) horalku. Najprv sa jeho riešenie stretne s riešením úžasnosti \(1\) a ľahko sa dostane do ďalšieho kola. Tam sa ale stretne s riešením úžasnosti \(4\) a bude musieť obetovať horalku. Pri pozícií \(3\) a \(4\) bude treba obetovať horalku hneď v prvom kole kvôli riešeniu úžasnosti \(4\) a potom aj kvôli riešeniu úžasnosti \(3\) (ktoré vyhralo súboj v prvej dvojici). Konkrétne, ak by Romanko začínal na tretej pozícií, na testovači by boli úžasnosti riešení v poradí \(1\) \(3\) \(2\) \(4\).