Lexicographically Smallest Transformation

Given a dictionary of n distinct words each of length m consisting of lowercase English letters, you are allowed to perform the following operation arbitrarily many times (possibly zero): choose any word from the dictionary and swap any two characters in that word. This operation allows you to arbitrarily permute the characters of any given word.

For each 1 ≤ i ≤ n, determine whether it is possible to obtain a new list of words \(w'_1, w'_2, \ldots, w'_n\) (by applying the allowed operations independently on each word) such that for every \(j \neq i\), the word \(w'_i\) is lexicographically smaller than \(w'_j\). In the case n=1, we define the property to hold automatically.

Recall that for two strings of equal length \(s=s_1s_2\cdots s_L\) and \(t=t_1t_2\cdots t_L\), we say \(s\) is lexicographically smaller than \(t\) if and only if there exists an index \(i\) such that \(s_1=t_1, s_2=t_2,\ldots, s_{i-1}=t_{i-1}\) and \(s_i < t_i\) (according to the alphabetical order).

Hint: Since each allowed operation is merely a swap, each word can be rearranged into any permutation of its characters. In particular, the lexicographically smallest permutation of a word \(w\) is obtained by sorting its characters in ascending order. Similarly, the lexicographically largest permutation is obtained by sorting its characters in descending order.

For a candidate word \(w_i\), if we choose \(w'_i\) to be the smallest permutation (i.e. the sorted string), then for every other word \(w_j\) (with \(j \neq i\)) we need to choose a permutation \(w'_j\) such that \(w'_j > w'_i\). A necessary and sufficient condition for this is that the lexicographically largest permutation of \(w_j\) is greater than \(w'_i\). Therefore, for each \(w_i\), output "YES" if for every \(j \neq i\), the largest permutation of \(w_j\) is lexicographically greater than the smallest permutation of \(w_i\); otherwise, output "NO". As mentioned, for \(n=1\), always output "YES".

inputFormat

The first line contains two space-separated integers \(n\) and \(m\) (the number of words and the length of each word).

Each of the next \(n\) lines contains a word of length \(m\) consisting of lowercase English letters.

outputFormat

Output \(n\) lines. The \(i\)-th line should be "YES" if it is possible to arrange the words so that the \(i\)-th word becomes strictly lexicographically smaller than every other word after the allowed operations, and "NO" otherwise.

sample

1 5
abcde

YES