Brazilian FootXOR

시간 제한0.5초메모리 제한2048 MB

요약

N개의 이진 벡터를 같은 크기의 두 팀으로 나눠 XOR이 같게 만들거나 불가능을 보고하는 문제.

난이도: 어려움10점 중 8점
유형: 수학, 동적 계획법, 비트 연산
정답자: 아직 제출이 없습니다

문제

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 ≤ N, K ≤ 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.

예제4

예제 1
입력
```
5 3
101
001
010
011
000
```
예상 출력
```
01221
```
예제 2
입력
```
3 2
01
10
11
```
예상 출력
```
*
```
예제 3
입력
```
4 3
011
000
100
011
```
예상 출력
```
1002
```
예제 4
입력
```
1 3
000
```
예상 출력
```
*
```