Have you ever used the chat application QQ? Well, in a chat group of QQ, administrators have permission to muzzle a user for some days.

There is a famous activity called ''Fudu'', which means repeating the sentence from the last guy sent.

As we all known, the penultimate person who do ''Fudu'' will be muzzled.

But Administrator Mieputrygub Bot thinks it's too boring, so he decided to muzzle the last -th person who do ''Fudu''.

Now, there are persons in a chat group who want to do ''Fudu''. If few people participate in ''Fudu'', it will be boring, so the number of participants will be greater than or equal to . If everyone does ''Fudu'', it is certain that existing a man who is the last -th.

However, the way they do ''Fudu'' is unusual, there will be several rounds. In each round, persons perform the following actions in sequence.

- If he did ''Fudu'' in the any previous rounds, he can't do ''Fudu'' in this round. It means each person can do ''Fudu'' only once.

- Otherwise, he can choose whether to do ''Fudu''.

If there is a round nobody do ''Fudu'', the process of doing ''Fudu'' will end.

For the person , if he is the -th person to do ''Fudu'', he can get bottles of Ice Black Tea.

However, if he was the last -th person to do ''Fudu'', he will be muzzled, not get any Ice Black Tea. He also need to give Mieputrygub Bot bottles of Ice Black Tea.It means he get bottles of Ice Black Tea.

If the last -th person does not exist, nobody will be muzzled.

Everyone wants to maximize the amount of Ice Black Tea they can get, you need to find out how much Ice Black Rea that each person can get finally.

The first line contains two postive integers  ().

Next  lines, -th line contains  postive integers  ().

For , .

Output one line with  integers, -th integers means the number of Ice Black Tea -th person will get.

3 2
1 14 5
141 9 1
9 8 10

1 0 0

The first person in the first round will do "Fudu" and get  bottle of Ice Black Tea.
And the remaining two are holding each other back.(If someone first do "Fudu" in this round , then another one can do "Fudu" in the next round to let first one be the last -th person who do "Fudu")

5 3
1000 4 3 2 1
4 1000 3 2 1
4 3 1000 2 1
4 3 2 1000 1
4 3 2 1 1000

1000 1000 0 0 0