Чтобы монстры из Внешнего мира смогли завоевать Землю, они должны одержать десять побед подряд в Смертельной Битве. Турниры проводятся раз в поколение, и бойцы Земли потерпели уже девять поражений. Настал час решающей Смертельной Битвы.

В Смертельной Битве участвуют N монстров и M лучших бойцов Земли. По правилам турнира, каждый монстр должен драться с одним из людей (все монстры с разными людьми). В случае если хотя бы один монстр одержит победу, то Земля навеки перейдёт во владение ужасного императора Внешнего мира. Впрочем, за людьми остаётся право выбора соперников и очерёдности боёв.

Бог Рейден, покровитель Земли, должен выбрать бойцов так, чтобы все люди одержали победу над соперниками. Для каждого из бойцов Земли известно, каких монстров он способен победить. Для начала, требуется выбрать пару соперников на первый бой.

Так, Лю Кэн хочет драться с Горо, но он единственный боец, способный победить Шан Цунга, в то время как Горо может быть повержен и другими бойцами, например, Джонни Кейджем. Поэтому первый бой между Лю Кэном и Горо даже в случае победы Лю Кэна неизбежно приведёт к захвату Земли, так как затем Шан Цунг одержит победу над своим соперником.

Определите, какие пары ни в коем случае не должны быть выбраны Рейденом, чтобы у людей остался шанс сохранить свою свободу.

В первой строке даны целые числа N и M. 1 ≤ N ≤ 300; N ≤ M ≤ 1500. Далее приведена матрица A из нулей и единиц размера N × M. A_ij = 1, если и только если j-й боец Земли способен одержать победу над i-м монстром.

Выведите матрицу B размера N × M. B_ij должно равняться единице, если на первый бой не может быть выбрана пара соперников (i, j), и нулю в противном случае.