ENG  RUSTimus Online Judge
Online Judge
Problems
Authors
Online contests
About Online Judge
Frequently asked questions
Site news
Webboard
Links
Problem set
Submit solution
Judge status
Guide
Register
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules

Ural SU contest. Petrozavodsk training camp. Summer 2008

About     Problems     Submit solution     Judge status     Standings
Contest is over

G. Mortal Kombat

Time limit: 1.0 second
Memory limit: 64 MB

Background

Once every generation, there is a tournament known as Mortal Kombat, which was designed by the Elder Gods for the main purpose to save Earthrealm from the dark forces of Outworld. If the forces of Outworld win the tournament ten consecutive times, the Emperor will be able to invade and conquer Earthrealm. Thus far, Outworld has won nine straight victories, making the upcoming tournament the tenth, and possibly final one, for the Earthrealm.

From Wikipedia, the free encyclopedia

Problem

There are N monsters and M best human fighters participating in the Mortal Kombat. According to the tournament rules, each monster should fight one of the humans (different monsters should fight different humans). If at least one monster wins, the Eathrealm will be conquered by the Emperor of the Outworld. However, the humans can choose the competitors and the order of battles.
The thunder god Raiden, protector of the Earthrealm, should choose the fighters in such a way that all Earth warriors will win their battles. For each monster and each Earth warrior it is known whether the Earth warrior can win the monster. First of all, the fighters for the first battle should be chosen.
For example, suppose that Liu Kang wants to fight Goro, but he is the only warrior able to defeat Shang Tsung, while Goro can be defeated by other warriors, such as Johnny Cage. So, even if Liu Kang will defeat Goro in the first battle, it will inevitably lead to the conquest of the Earth, because later Shang Tsung will defeat his opponent. This means that the pair Liu Kang vs. Goro should not be selected for the first fight.
Find out which pairs cannot be chosen by Raiden if he wants to save the freedom of humanity.

Input

The first line contains integers N and M (1 ≤ N ≤ 300; NM ≤ 1500). Next lines contain the binary matrix A with N rows and M columns. Aij = 1 if and only if j-th Earth warrior can defeat i-th monster.

Output

Output matrix B with N rows and M columns. Bij should be equal to one if the first battle cannot be held between i-th monster and j-th human, and zero otherwise.

Samples

inputoutput
4 4
1111
1000
1111
1111
1000
0111
1000
1000
4 5
10000
10000
10000
10000
11111
11111
11111
11111
Problem Author: Magaz Asanov (prepared by Alexander Ipatov)
Problem Source: Ural SU Contest. Petrozavodsk Summer Session, August 2008
To submit the solution for this problem go to the Problem set: 1676. Mortal Kombat