P15096 [ICPC 2025 LAC] Brazilian 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$ 被分配到第一支队伍、第二支队伍或者两支队伍都不分配。如果存在多种解决方案，输出任意一种即可。 如果无法满足教练的条件，则输出字符“*”（星号）。

翻译由 DeepSeek V3 完成