Little S has a dictionary containing $n$ distinct words $w_1, w_2, \dots, w_n$, each of length $m$. Each word is a string consisting of lowercase English letters.

Little S can perform the following operation any number of times (including zero): choose any word in the dictionary and swap any two characters within it.

For each $1 \le i \le n$, Little S wants to know if it is possible to obtain a new set of $n$ words $w'_1, w'_2, \dots, w'_n$ through the above operations such that for every $j \neq i$, $w'_i$ is lexicographically smaller than $w'_j$. For the case $n = 1$, we define the property to be naturally satisfied.

For two strings of the same length $s = s_1s_2 \dots s_L$ and $t = t_1t_2 \dots t_L$, string $s$ is said to be lexicographically smaller than string $t$ if and only if the following condition holds: there exists a position $i$ such that $s$ and $t$ are identical before the $i$-th character, and $s_i < t_i$, meaning the lowercase letter $s_i$ precedes $t_i$ in the English alphabet.

Input

The input consists of $n$ and $m$ on the first line, representing the number of words and the length of each word, respectively.

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

Output

Output a single line containing a 01 string $a$ of length $n$. For each $1 \le i \le n$, if the property described in the problem holds, $a_i = 1$, otherwise $a_i = 0$.

Examples

Input 1

4 7
abandon
bananaa
baannaa
notnotn

Output 1

1110

Note 1

• Without any operations, the first word is lexicographically smallest, so the first character is 1.
• By swapping the first two characters of bananaa and the third and sixth characters of abandon, we obtain abondan, abnanaa, baannaa, notnotn. At this point, the second word is lexicographically smallest, so the second character is 1.
• By swapping the first and last characters of baannaa to get aaannab and leaving the other strings unchanged, the third word is lexicographically smallest, so the third character is 1.
• No matter what operations are performed, the fourth word cannot be smaller than the second word, so the fourth character is 0.

Examples 2-4

See the files dict/dict2.in and dict/dict2.ans, dict/dict3.in and dict/dict3.ans, and dict/dict4.in and dict/dict4.ans in the contestant directory. These examples satisfy the constraints of test cases 4, 7, and 10, respectively.

Constraints

For all test data, it is guaranteed that $1 \le n \le 3,000$, $1 \le m \le 3,000$, and all $w_i$ are distinct strings of length $m$ consisting of lowercase letters.