A. 词典
time limit per test
1 second
memory limit per test
512 megabytes
input
dict.in
output
dict.out

小 S 的词典里有 $$$n$$$ 个两两不同的、长度均为 $$$m$$$ 的单词 $$$w_1,w_2,\cdots,w_n$$$。每个单词都是一个小写字母构成的字符串。

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

对于每个 $$$1 \le i \le n$$$，小 S 想知道，是否可以通过以上操作得到新的 $$$n$$$ 个单词 $$$w'_1,w'_2,\cdots , w'_n$$$，使得对于每个 $$$j \neq i$$$，$$$w'_i$$$ 的字典序比 $$$w'_j$$$ 都要小。对于 $$$n=1$$$ 的情况，我们约定：上述性质是自然成立的。

对于两个同样长度的字符串 $$$s = s_1s_2\cdots s_L$$$ 和 $$$t = t_1t_2 \cdots t_L$$$，称字符串 $$$s$$$ 字典序小于字符串 $$$t$$$，当且仅当以下条件成立：存在位置 $$$i$$$，在第 $$$i$$$ 个字符之前 $$$s$$$ 和 $$$t$$$ 都相同，而且 $$$s_i \lt t_i$$$，即小写字母 $$$s_i$$$ 在英文字母顺序中先于 $$$t_i$$$。

Input

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

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

Output

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

Example
Input
4 7
abandon
bananaa
baannaa
notnotn
Output
1110
Note

【样例解释 #1】

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

【数据范围】

对于所有测试数据，保证：$$$1 \le n \le 3000$$$，$$$1 \le m \le 3000$$$，$$$w_i$$$ 为长度为 $$$m$$$ 的小写字母字符串且两两不同。