题目描述

Alex is coaching the famous Brazilian FootXOR Club. For today’s training, they want to organize a match between two teams selected from the $N$ club members. To ensure a fair match, the two teams must be balanced.

Each club member has a set of abilities represented as a $K$-digit binary string. Each digit corresponds to a characteristic that the player may or may not have. Surprisingly, it is not the quantity of players having each characteristic that matters when deciding whether two teams are balanced: the important thing is the parity of that quantity.

Two teams are considered balanced if they have the same number of players and the bitwise XOR of the ability strings of all players in the first team is equal to the bitwise XOR of the ability strings of all players in the second team. Of course, each club member can only be assigned to at most one team and, for a match to happen, teams cannot be empty.

Alex is really busy right now. As their coaching assistant, you must determine how to assign players to the two teams. If it is impossible to fulfill the coach’s conditions, you must inform the coach accordingly.

输入格式

The first line contains two integers $N$ and $K$ ($1 \le N, K \le 1500$), indicating respectively the number of club members and the number of binary digits used to represent their abilities. Each club member is identified by a distinct integer from $1$ to $N$.

The $i$-th of the next $N$ lines contains a $K$-digit binary string $A_i$, representing the abilities of club member $i$. Note that $A_i$ has a fixed length and so it may contain leading zeros.

输出格式

Output a single line with a string of length $N$ if it is possible to fulfill the coach’s conditions. In this case, the $i$-th character of the string must be a digit “1”, “2” or “0”, indicating respectively that club member $i$ is assigned to the first team, to the second team, or to none of the two teams. If there are multiple solutions, output any of them.

If the coach’s conditions cannot be honored, output the character “*” (asterisk) instead.

5 3
101
001
010
011
000

01221

3 2
01
10
11

*

4 3
011
000
100
011

1002

1 3
000

*