Codeforces Round #486 (Div. 3)-B. Substrings Sort

You are given $nn strings. Each string consists of lowercase English letters. Rearrange (reorder) the given strings in such a way that for every string, all strings that are placed before it are its substrings.$

String $aa is a substring of string bb if it is possible to choose several consecutive letters in bb in such a way that they form aa. For example, string "for" is contained as a substring in strings "codeforces", "for" and "therefore", but is not contained as a substring in strings "four", "fofo" and "rof".$

Input

The first line contains an integer $nn (1\leqn\leq1001\leqn\leq100) — the number of strings.$

The next $nn lines contain the given strings. The number of letters in each string is from 11 to 100100, inclusive. Each string consists of lowercase English letters.$

Some strings might be equal.

Output

If it is impossible to reorder $nn given strings in required order, print "NO" (without quotes).$

Otherwise print "YES" (without quotes) and $nn given strings in required order.$

Examples

input

Copy

5
a
aba
abacaba
ba
aba

output

Copy

YES
a
ba
aba
aba
abacaba

input

Copy

5
a
abacaba
ba
aba
abab

output

Copy

NO

input

Copy

3
qwerty
qwerty
qwerty

output

Copy

YES
qwerty
qwerty
qwerty

Note

In the second example you cannot reorder the strings because the string "abab" is not a substring of the string "abacaba".

被HACK掉了。。。只能说数据太水了。。。发现自己的程序问题还这么大，还是太菜了。

本题题意就是是否可以把所给的N个序列摆放成上面的序列是下面序列的子序列

开始想了半天。。。怎么找啊。。。这™序列这么多，要我一个一个比？后来发现，你只需要按照从小到大的序列长度排序就好了啊。。。然后从下往上，两个判断是否上面的那么个序列是下面序列的子序列。o(n)操作嘛，小case.

被HACK掉原因就是我匹配那里写错了

正确写匹配姿势:

 1  for (int i=0; i<=word[p].len-word[p-1].len; i++)//每个头位置的指针
 2     {
 3         flag=0;
 4         pi=i;//检查在I为头的情况下的是否匹配的指针
 5         for(int j=0; j<word[p-1].len;j++)
 6         {
 7             if(word[p].sub[pi]!=word[p-1].sub[j])
 8             {
 9                 flag=1;//如果有不同
10                 break;
11             }
12             else
13             {
14                 pi++;//继续匹配
15                 continue;
16             }
17         }
18         if (flag==0)break;
19     }

emmmmm最后AC代码

#include<iostream>
#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;
struct Node
{
    char sub[105];
    int len;
} word[105];
bool cmp(Node x,Node y)
{
    return x.len<y.len;//按照长度排序
}
int pp(int p)
{
    int flag;
    int pi;
    for (int i=0; i<=word[p].len-word[p-1].len; i++)
    {
        flag=0;
        pi=i;
        for(int j=0; j<word[p-1].len;j++)
        {
            if(word[p].sub[pi]!=word[p-1].sub[j])
            {
                flag=1;
                break;
            }
            else
            {
                pi++;
                continue;
            }
        }
        if (flag==0)break;
    }
    if (flag==0)return 0;
    else return 1;
}
int main()
{
    int n;
    int lens;
    int flag;
    while (~scanf("%d",&n))
    {
        flag=0;
        for (int i=0; i<n; i++)
        {
            scanf("%s",word[i].sub);
            lens=strlen(word[i].sub);
            word[i].len=lens;
        }
        sort(word,word+n,cmp);
        for (int i=n-1; i>0; i--)
        {
            if(pp(i)!=0){
            flag=1;
            break;
            }
        }
        if(flag==1)printf("NO\n");
        else
        {
            printf("YES\n");
            for (int i=0; i<n; i++)
            {
                printf("%s\n",word[i].sub);
            }
        }
    }
    return 0;
}