题目描述

小 S 的词典里有 $n$ 个两两不同的、长度均为 $m$ 的单词 $w_1$, $w_2$, · · · , $w_n$。每个单词都是一个小写字母构成的字符串。 小 S 可以做以下操作任意多次（可以不做）：选择词典中的任意一个单词，交换其中任意两个字符。 对于每个 $1 ≤ i ≤ n$，小 S 想知道，是否可以通过以上操作得到新的 $n$ 个单词$w'_1$, $w'_2$, · · · , $w'_n$，使得对于每个 $j≠ i$，$w'_i$ 的字典序比 $w'_j$ 都要小。对于$n = 1$ 的情况，我们约定：上述性质是自然成立的。 对于两个同样长度的字符串 $s = s_1s_2 · · · s_L$ 和 $t = t_1t_2 · · ·t_L$，称字符串 $s$ 字典序小于字符串 $t$，当且仅当以下条件成立：存在位置 $i$，在第$i$ 个字符之前 $s$ 和 $t$ 都相同，而且 $s_i < t_i$，即小写字母 $s_i$ 在英文字母顺序中先于 $t_i$。

输入

输入的第一行包含两个正整数 $n$ 和 $m$，分别表示单词个数和单词长度。 接下来 $n$ 行，每行包含一个长度为 $m$ 的小写字母字符串 $w_i$，表示一个单词。

输出

输出一行，其中包含一个长度为 $n$ 的 $01$ 字符串 $a$；对于 $1 ≤ i ≤ n$，如果题目 描述中的性质成立，则 $a_i = 1$，否则 $a_i = 0$。

输入样例

4 7
abandon
bananaa
baannaa
notnotn

输出样例

1110

提示

【样例 1 解释】 • 不做任何操作，第一个单词字典序最小，因此输出第一个字符为 $1$； • 交换 bananaa 的前两个字符以及 abandon 的第三个和第六个字符，得到 abondan,abnanaa, baannaa, notnotn，此时第二个单词字典序最小，因此输出第二个字符为 $1$； • 交换 baannaa 的第一个和最后一个字符得到 aaannab，其余字符串不变，此时第三个单词字典序最小，因此输出第三个字符为 $1$； • 无论如何操作，第四个单词不会小于第二个单词，因此输出第四个字符为 $0$。 【数据范围】 对于所有测试数据，保证：$1 ≤ n ≤ 3, 000$，$1 ≤ m ≤ 3, 000$，$w_i$ 为长度为 $m$ 的小写字母字符串且两两不同。

评测数据说明

本题使用按题意独立构造、以独立程序核对的训练数据及公开样例，共5个测试点，非原站或官方原始数据。总分100分。