ENG  RUS Timus Online Judge
Online Judge
Problems
Authors
Online contests
Site news
Webboard
Problem set
Submit solution
Judge status
Guide
Register
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules

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.

### 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