Problem Description

Xiao S has $n$ pairwise distinct words $w_1, w_2, \cdots, w_n$ in the dictionary, each with length $m$. Each word is a string consisting of lowercase letters.

Xiao S may perform the following operation any number of times (possibly zero times): choose any word in the dictionary and swap any two characters in it.

For each $1 \le i \le n$, Xiao S wants to know whether it is possible, through the operations above, to obtain $n$ new words $w'_1, w'_2, \cdots, w'_n$ such that for every $j \ne i$, $w'_i$ is lexicographically smaller than $w'_j$. For the case $n = 1$, we agree that the property above naturally holds.

For two strings of the same length $s = s_1 s_2 \cdots s_L$ and $t = t_1 t_2 \cdots t_L$, we say that $s$ is lexicographically smaller than $t$ if and only if the following holds: there exists a position $i$ such that $s$ and $t$ are identical before the $i$-th character, and $s_i < t_i$, i.e., the lowercase letter $s_i$ comes before $t_i$ in alphabetical order.

Input Format

The first line contains two positive integers $n$ and $m$, representing the number of words and the length of each word.

The next $n$ lines each contain a lowercase string $w_i$ of length $m$, representing a word.

Output Format

Output one line containing a 01 string $a$ of length $n$. For $1 \le i \le n$, if the property described in the statement holds, then $a_i =$ 1; otherwise, $a_i =$ 0.

4 7
abandon
bananaa
baannaa
notnotn

1110

Hint

[Sample Explanation #1]

• Without any operation, the first word is lexicographically smallest, so the first character of the output is 1.
• Swap the first two characters of bananaa, and swap the third and sixth characters of abandon, obtaining abondan, abnanaa, baannaa, notnotn. Now the second word is lexicographically smallest, so the second character of the output is 1.
• Swap the first and last characters of baannaa to get aaannab, leaving the other strings unchanged. Now the third word is lexicographically smallest, so the third character of the output is 1.
• No matter how you operate, the fourth word will not be smaller than the second word, so the fourth character of the output is 0.

[Sample Explanation #2]

This sample satisfies the limits of test point $4$.

[Sample Explanation #3]

This sample satisfies the limits of test point $7$.

[Sample Explanation #4]

This sample satisfies the limits of test point $10$.

[Constraints]

For all testdata, it is guaranteed that: $1 \le n \le 3000$, $1 \le m \le 3000$, each $w_i$ is a lowercase string of length $m$, and all words are pairwise distinct.

Translated by ChatGPT 5