La firma de publicitate „Catchy” s-au primit N comenzi pentru realizarea de bannere publicitare (acestea au fost numerotate de la 1 la N). Angajații firmei au observat că se poate economisi foarte mult material dacă refolosesc cuvinte care au fost scrise pe bannere publicitare mai vechi, care au fost deja folosite, au fost recuperate şi au fost depozitate în magazia firmei. Acest lucru este posibil, deoarece ei folosesc întotdeauna acelaşi font, aceeaşi culoare şi aceeaşi dimensiune pentru textele scrise pe bannere. În magazia firmei sunt depozitate K bannere vechi. Cuvintele de pe acestea pot fi decupate integral şi reasamblate pentru a forma textul noilor bannere comandate. Caracterele speciale care separă cuvintele nu vor fi refolosite, pentru că nu este rentabil. Pentru că își doresc să fie cât mai eficienți, ei vor realiza iniţial dintre bannerele comandate doar un singur banner pentru care textul este format numai din cuvinte care se află deja scrise pe bannerele depozitate în magazie. Dacă există mai multe astfel de bannere, vor alege un banner pentru care numărul de exemplare identice ce pot fi realizate este maxim. Şi dacă şi în acest caz există mai multe bannere posibile, se va realiza bannerul cu numărul de ordine cel mai mic.

Cerința

Cunoscând textele scrise pe cele K bannere depozitate în magazia firmei, precum și textele care trebuie să fie scrise pe cele N bannere nou comandate, scrieţi un program care să determine bannerul care urmează să fie realizat, în condiţiile descrise în enunţul problemei.

Date de intrare

Pe prima linie a fișierului catchy.in se află numărul natural K reprezentând numărul de bannere din magazie. Pe următoarele K linii sunt scrise textele bannerelor aflate în magazia firmei, câte un text pe o linie. Pe a treia linie este scris un număr natural N reprezentând numărul de bannere noi. Pe următoarele N linii sunt scrise textele de pe bannerele noi, câte un text pe o linie.

Date de ieșire

Fișierul de ieşire catchy.out va conţine două linii. Pe prima linie va fi scris numărul de ordine al bannerului ce va fi realizat. Pe a doua linie va fi scris numărul maxim de exemplare identice ce pot fi realizate din acest banner.

Restricții și precizări

• 1 ≤ k, n ≤ 150;
• Textul scris pe orice banner este nevid şi are cel mult 1500 de caractere cu coduri ASCII cuprinse între 32 şi 127;
• Caracterele : , : ; ) ( . ? ! > < } { şi spaţiul sunt considerate caractere speciale, deoarece sunt separatori;
• Un cuvânt este format dintr-o succesiune nevidă de maxim 25 de caractere diferite de separatori;
• Oricare două cuvinte succesive în text sunt separate de unul sau mai mulţi separatori;
• Se face distincţie între literele mici şi literele mari;
• Pentru datele de test va exista cel puţin un banner care poate să fie realizat;

Exemplu

catchy.in

5
Acum avem multe  de castigat,    "recuperand" aceste cuvinte.
Folosim cuvinte, multe cuvinte, cuvinte din multe bannere folosite.
cuvintele folosite sunt multe valoroase; ele se 'pastreaza'.
Noi avem multe bannere in magazie care pot fi folosite.
Cuvintele sunt: cu litere mari, mici, acelasi font, fara diacritice.
6
dorim s-avem bannere valoroase.
multe cuvinte sunt valoroase.
sunt   multe, multe cuvinte.
Noi,   "recuperand" cuvintele, avem de castigat.
Vasile e de acord
avem multe.

catchy.out

3
2

Explicație

Există 5 bannere în magazie şi avem 6 comenzi pentru bannere noi. Bannerul nou cu numărul de ordine 1 nu poate fi realizat deoarece cuvintele din care este format nu se regăsesc toate în textul bannerelor vechi (cuvintele dorim şi s-avem nu există). De asemenea bannerul nou cu numărul de ordine 6 nu poate fi realizat. Bannerele cu numerele de ordine 2, 3 şi 4 pot fi realizate. Bannerul 2 poate fi realizat într-un singur exemplar, deoarece cuvântul valoroase poate fi decupat o singură dată. Bannerul 3 poate fi realizat în două exemplare:

Bannerul 4 poate fi realizat într-un singur exemplar. Bannerul 6 poate fi şi el realizat în două exemplare, dar deoarece bannerul 3 are numărul de ordine mai mic, îl vom alege pe acesta.

#include <bits/stdc++.h>


using namespace std;

ifstream cin("catchy.in");
ofstream cout("catchy.out");

struct cuv
{
    string c;
    int ap;
}a[3501];
cuv b[3501];
int n , k , na , nb , ales , rad , ns , nt;

string S[100001] , T[100001];
int apare(cuv a[] , int n , string s)
{
    for(int i = 1  ;i <= n ; i++)
        if(s == a[i].c) return i;
    return 0;
}

int cautarebinara(cuv a[] , int n , string s)
{
    int st = 1 , dr = n;
    while(st <= dr)
    {
        int m = (st + dr) / 2;
        if(a[m].c == s) return m;
        else if(a[m].c > s) dr = m - 1;
        else st = m + 1;
    }
    return 0;
}

int maimic(cuv a , cuv b)
{
    return a.c < b.c;
}
int main()
{
    cin >> k;
    cin.get();
    char s[1501] , sep[] = " ,:;)(.?!><}{";
    string cuv;
    for(int i = 1 ; i <= k ; i++)
    {
        cin.getline(s , 1501);
        char *p = strtok(s , sep);
        while(p)
        {
            S[++ns] = p;
            p = strtok(NULL , sep);
        }
    }
    sort(S + 1 , S + ns+1);
    na = 1;
    a[na].c = S[1];
    a[na].ap = 1;
    for(int i = 2 ; i <= ns ; i++)
        if(S[i] == S[i-1]) a[na].ap++;
        else
        {
            na ++;
            a[na].ap = 1;
            a[na].c = S[i];
        }
    cin >> n;
    cin.get();

    for(int i = 1 ; i <= n ; i++)
    {
        nt = 0;
        cin.getline(s , 1501);
        char *p = strtok(s , sep);
        while(p)
        {
            T[++nt] = p;
            p = strtok(NULL , sep);
        }
        sort(T + 1 , T + nt + 1);
        nb = 1;
        b[nb].c = T[1];
        b[nb].ap = 1;
        for(int i = 2 ; i <= nt ; i++)
            if(T[i] == T[i-1]) b[nb].ap++;
            else
            {
                nb ++;
                b[nb].ap = 1;
                b[nb].c = T[i];
            }

        int rmin= 100000;
        for(int j = 1 ; j <= nb ; j++)
        {
            int poz = cautarebinara(a , na , b[j].c);
            if(poz == 0) rmin = 0;
            else if(a[poz].ap / b[j].ap < rmin)
                rmin = a[poz].ap / b[j].ap;
        }
        if(rmin > rad)
        {
            rad = rmin;
            ales = i;
        }
    }
    cout << ales << endl << rad;

}