BerOS File Suggestion CodeForces - 1070H

Polycarp is working on a new operating system called BerOS. He asks you to help with implementation of a file suggestion feature.

There are nn files on hard drive and their names are f1,f2,…,fnf1,f2,…,fn. Any file name contains between 11 and 88 characters, inclusive. All file names are unique.

The file suggestion feature handles queries, each represented by a string ss. For each query ss it should count number of files containing ss as a substring (i.e. some continuous segment of characters in a file name equals ss) and suggest any such file name.

For example, if file names are "read.me", "hosts", "ops", and "beros.18", and the query is "os", the number of matched files is 22 (two file names contain "os" as a substring) and suggested file name can be either "hosts" or "beros.18".

Input

The first line of the input contains integer nn (1≤n≤100001≤n≤10000) — the total number of files.

The following nn lines contain file names, one per line. The ii-th line contains fifi — the name of the ii-th file. Each file name contains between 11 and 88 characters, inclusive. File names contain only lowercase Latin letters, digits and dot characters ('.'). Any sequence of valid characters can be a file name (for example, in BerOS ".", ".." and "..." are valid file names). All file names are unique.

The following line contains integer qq (1≤q≤500001≤q≤50000) — the total number of queries.

The following qq lines contain queries s1,s2,…,sqs1,s2,…,sq, one per line. Each sjsj has length between 11 and 88 characters, inclusive. It contains only lowercase Latin letters, digits and dot characters ('.').

Output

Print qq lines, one per query. The jj-th line should contain the response on the jj-th query — two values cjcj and tjtj, where

• cjcj is the number of matched files for the jj-th query,
• tjtj is the name of any file matched by the jj-th query. If there is no such file, print a single character '-' instead. If there are multiple matched files, print any.

Example

Input

4
test
contests
test.
.test
6
ts
.
st.
.test
contes.
st

Output

1 contests
2 .test
1 test.
1 .test
0 -
4 test.

题意

给你n个字符串 每次询问 每次询问给你一个字符串，问n个字符串中有几个出现过，随便输出一个

思路

n小字符串短，可以直接把n个字符串一次分解

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

char s[10004][10];
map<string,int> mp1;
map<string,int> mp2;

int main()
{
    int n,m,i,j,len,k,kk;
    int num;
    char str[10];
    string ss;
    scanf("%d",&n);
    for(kk=1;kk<=n;kk++)
    {
        scanf("%s",s[kk]);
        len = strlen(s[kk]);
        map<string ,int> mp;
        for(i=1;i<=len;i++)
        {
            for(j=0;j<=len-i;j++)
            {
                for(k=0;k<i;k++)
                {
                    str[k] = s[kk][j+k];
                }
                str[k] = '\0';
                ss = str;
                if(mp[ss]) continue;
                else mp[ss]++;
                mp1[ss]++;
                mp2[ss] = kk;
            }
        }
    }
    scanf("%d",&m);
    while(m--)
    {
        cin>>ss;
        printf("%d ",mp1[ss]);
        if(mp1[ss] == 0) printf("-\n");
        else printf("%s\n",s[mp2[ss]]);
    }
    return 0;
}