Lightbulbs
Летен Турнир по Информатика 2019
Time Limit: 2s, Memory Limit: 64MiB
Домът на Ели има L крушки. Те могат да бъдат включвани и изключвани ползвайки N ключа, всеки от които контролира под-множество от крушките. Недостиг на електро инсталацията на къщата е, че ако Ели ползва ключ, който включва крушка, която вече свети, тя изгаря и повече не може да бъде включена.

Различните крушки имат различна важност за Ели. Например, крушката в мазето, където тя слиза веднъж в годината, е далеч по-маловажна от крушката във всекидневната. Момичето ги е подредило по важност – първата крушка е най-важната, втората е по-малко важна и т.н., докато L-тата е най-малко важна.

Сега момичето иска да ползва ключовете по такъв начин, че да свети подмножество от крушките с най-голяма важност (като няма значение колко от останалите ще изгорят). За две подмножества A и B казваме, че A e по-важно от B ако най-важната крушка, която свети в едното, но не в другото, е в подмножество A.

Нека, например, в къщата на Ели има пет крушки и три ключа, като първият ключ контролира втората, третата, и петата крушка, вторият ключ контролира първата, третата и четвъртата, а третият – втората, четвъртата и петата. Има смисъл да ползваме втория ключ, тъй като той единствен контролира най-важната крушка. Ако освен него ползваме първия ключ, то ще изгорим третата крушка и ще светнем втората и петата. Ако означим светещите крушки с 1, а несветещите/изгорелите с 0, като важността на крушките намалява от ляво надясно, то така ще постигнем 11011. Ако пък вместо първия ключ ползваме третия ще постигнем 11101. Вторият вариант е за предпочитане, тъй като в него свети най-важната крушка, в която се различават (третата). Ако ползваме и трите ключа ще получим 10000, тъй като всяка крушка освен първата бива светната от поне два ключа.

По дадена схема кои крушки са контролирани от кои ключове, помогнете на Ели да определи най-важното подмножество от крушки, което може да свети след ползване на един или повече от ключовете.
Вход
На първия ред на стандартния вход ще бъдат зададени целите числа N и L – съответно броя ключове и броя крушки в къщата на Ели. На всеки от следващите N реда ще бъде зададена последователност от нули и единици с дължина L, указваща крушките, които контролира съответния ключ.
Изход
На стандартния изход изведете последователност от нули и единици с дължина L – оптималното под-множество от крушки, което може да свети след използване на един или повече от ключовете.
Ограничения
  • 1 ≤ N ≤ 50
  • 1 ≤ L ≤ 50
Примерен Вход Примерен Изход
3 5 01101 10110 01011 11101
10 20 00010111011100101010 11110001010110011110 00101010100100000100 11000000111011101000 01100101011001100100 11010010110010000100 01111111011000010001 00001010111010011111 11100011101000011011 10001000011001001111 11111101000011000110
Мрън!