#2040. 「NOIP 2023」词典

小 S 的词典里有 个两两不同的、长度均为 的单词 。每个单词都是一个小写字母构成的字符串。

小 S 可以做以下操作任意多次（可以不做）：选择词典中的任意一个单词，交换其中任意两个字符。

对于每个 ，小 S 想知道，是否可以通过以上操作得到新的 个单词 ，使得对于每个 ， 的字典序比 都要小。对于 的情况，我们约定：上述性质是自然成立的。

对于两个同样长度的字符串 和 ，称字符串 字典序小于字符串 ，当且仅当以下条件成立：存在位置 ，在第 个字符之前 和 都相同，而且 ，即小写字母 在英文字母顺序中先于 。

从文件 dict.in 中读入数据。

输入的第一行包含两个正整数 和 ，分别表示单词个数和单词长度。

接下来 行，每行包含一个长度为 的小写字母字符串 ， 表示一个单词。

输出到文件 dict.out 中。

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

样例 1 输入

4 7
abandon
bananaa
baannaa
notnotn

样例 1 输出

1110

样例 1 解释

• 不做任何操作，第一个单词字典序最小，因此输出第一个字符为 1；
• 交换 bananaa 的前两个字符以及 abandon 的第三个和第六个字符，得到 abondan, abnanaa, baannaa, notnotn，此时第二个单词字典序最小，因此输出第二个字符为 1；
• 交换 baannaa 的第一个和最后一个字符得到 aaannab，其余字符串不变，此时第三个单词字典序最小，因此输出第三个字符为 1；
• 无论如何操作，第四个单词不会小于第二个单词，因此输出第四个字符为 0。

样例 2

见附加文件中的 dict/dict2.in 和 dict/dict2.ans。

该组样例满足测试点 的限制。

样例 3

见附加文件中的 dict/dict3.in 和 dict/dict3.ans。

该组样例满足测试点 的限制。

样例 4

见附加文件中的 dict/dict4.in 和 dict/dict4.ans。

该组样例满足测试点 的限制。

对于所有测试数据，保证：，， 为长度为 的小写字母字符串且两两不同。