巴西 FootXOR - 题目

Alex 正在执教著名的巴西 FootXOR 俱乐部。在今天的训练中，他们想要从 $N$ 名俱乐部成员中选出两支队伍进行比赛。为了确保比赛公平，两支队伍必须保持平衡。

每位俱乐部成员都有一组能力，用一个 $K$ 位的二进制字符串表示。每一位对应一个球员可能拥有或不拥有的特征。令人惊讶的是，在决定两支队伍是否平衡时，拥有某种特征的球员数量并不重要，重要的是该数量的奇偶性。

如果两支队伍的人数相同，且第一支队伍所有球员能力字符串的按位异或和等于第二支队伍所有球员能力字符串的按位异或和，则认为这两支队伍是平衡的。当然，每位俱乐部成员最多只能被分配到一支队伍中，且为了进行比赛，队伍不能为空。

Alex 现在非常忙。作为他的教练助理，你必须确定如何将球员分配到这两支队伍中。如果无法满足教练的条件，你必须相应地通知教练。

第一行包含两个整数 $N$ 和 $K$ ($1 \le N, K \le 1500$)，分别表示俱乐部成员的数量和用于表示他们能力的二进制位数。每位俱乐部成员由 $1$ 到 $N$ 之间的一个不同整数标识。

接下来的 $N$ 行中，第 $i$ 行包含一个 $K$ 位的二进制字符串 $A_i$，表示俱乐部成员 $i$ 的能力。注意 $A_i$ 的长度是固定的，因此它可能包含前导零。

如果能够满足教练的条件，输出一行长度为 $N$ 的字符串。在这种情况下，字符串的第 $i$ 个字符必须是数字“1”、“2”或“0”，分别表示俱乐部成员 $i$ 被分配到第一支队伍、第二支队伍，或不分配到任何一支队伍。如果存在多种方案，输出其中任意一种即可。

如果无法满足教练的条件，则输出字符“*”（星号）。

1 3
000

QOJ.ac