5. Éra vyhýbania

Jožo nemá rád svojich spolužiakov. Neustále im robí zle a najradšej by ich vôbec nevidel. Keď je s nejakým spolužiakom na prednáške, radšej zaspí. Rozhodol sa preto, že svoj nový rozvrh zostaví tak, aby bol s každým spolužiakom čo nejmenej.

Nažhavil teda larsa¹ a začal hackovať univerzitné účty svojich nenávidených spolužiakov. Netrvalo dlho, aby zistil rozvrhy všetkých ľudí, s ktorými sa nechce stretávať.

Počas hackovania sa Jožovi vybil počítač a nabíjačku má niekde hlboko v batohu. Nepripadá teda do úvahy, aby si tento optimalizačný problém vyriešil sám. Zostavíte Jožovi jeho nový rozvrh?

Úloha

Jožo vám dodal rozvrhy svojich \(n\) spolužiakov. Existuje \(k\) predmetov. Očíslujme si ich od \(1\) po \(k\).

Každý spolužiak na každý predmet buď chodí, alebo nechodí. Reprezentujme si teda predmety každého spolužiaka binárnym reťazcom dĺžky \(k\). Ak daný spolužiak chodí na predmet číslo \(i\), tak v binárnom reťazci bude na \(i\)-tej pozícii \(1\), ináč bude na \(i\)-tej pozícii \(0\).

Vzdialenosť od spolužiaka Jožo definuje ako počet predmetov, na ktoré spolužiak chodí a Jožo nechodí, alebo spolužiak nechodí a Jožo chodí. Ináč povedané, keď si napíšeme spolužiakov a Jožov rozvrh pod seba, tak vzdialenosť od spolužiaka bude počet pozícií, na ktorých sa tieto rozvrhy líšia.

Vašou úlohou bude zostaviť Jožov rozvrh tak, aby bola minimálna vzdialenosť od spolužiaka (spomedzi všetkých spolužiakov) čo najväčšia.

Formát vstupu

Na prvom riadku dostanete čísla \(n\) – počet spolužiakov a \(k\) – počet predmetov. Platí, že \(1 \leq n \leq 100\,000\) a \(1 \leq k \leq 20\)

Nasleduje \(n\) riadkov. Na každom z nich je binárny reťazec dĺžky \(k\). Na \(i\)-tom z týchto \(n\) riadkov je popis rozvrhu \(i\)-teho spolužiaka vo vyššie popísanom formáte.

Formát výstupu

Na jediný riadok výstupu vypíšte nový Jožov rozvrh. Ak takých rozvrhov existuje viac, vypíšte z nich lexikograficky najmenší.

Hodnotenie

Sú 4 sady vstupov. Platia v nich nasledovné obmedzenia:

Príklady

Input:

3 5
01101
10101
00011

Output:

11000

Input:

1 6
011011

Output:

100100