Corina are un text format din mai multe cuvinte separate între ele printr-un spațiu, pentru care trebuie să utilizeze cuvintele aflate pe poziţii consecutive. Se știe că pentru două cuvinte pe care le vom numi x și y:

• cuvântul x=x[0]x[1]...x[n-1] este prefix al cuvântului y=y[0]y[1]...y[m-1], dacă x[0]=y[0], x[1]= y[1],…, x[n-1]=y[n-1]
• cuvântul x=x[0]x[1]...x[n-1] este sufix al cuvântului y=y[0]y[1]...y[m-1], dacă există un indice i, (0≤ i≤ m-1), astfel încât x[0]=y[i], x[1]= y[i+1],…, x[n-1]= y[m-1].

Cerința

Scrieţi un program care determină pentru un text dat, format din mai multe cuvinte separate între ele printr-un spațiu, două cerințe:

• cerința 1: câte perechi de cuvinte, notate x și y, aflate pe poziții consecutive în text au proprietatea: x este sufix al lui y sau x este prefix al lui y.
• cerința 2 : care este perechea de cuvinte, aflate pe poziții consecutive în text, care conține cele mai multe caractere.

Date de intrare

Fișierul de intrare cuvinte6.in conține pe prima linie un text, format din mai multe cuvinte separate între ele printr-un spațiu și pe a doua linie conține un număr natural t, care reprezintă cerința (dacă t=1 se va rezolva cerința 1, dacă t=2 se va rezolva cerința 2).

Date de ieșire

Fișierul de ieșire cuvinte6.out va conține pe prima linie, pentru cerința 1, un număr natural, ce reprezintă numărul de perechi de cuvinte, notate x și y, aflate pe poziții consecutive în text care au proprietatea: x este sufix al lui y sau x este prefix al lui y.

Fișierul de ieșire cuvinte6.out va conține pe prima linie, pentru cerința 2 două cuvinte, separate printr-un spațiu, ce reprezintă perechea de cuvinte, aflate pe poziții consecutive în text, care conține cele mai multe caractere.

Restricții și precizări

• Textul dat conține cel mult 500 de caractere
• Fiecare cuvânt din text este format numai din litere mici ale alfabetului englez
• Fiecare cuvânt din text conține cel puțin o literă și cel mult 20 de litere
• Pentru cerința 2, dacă textul dat are mai multe perechi de cuvinte, aflate pe poziții consecutive în text, care conțin cele mai multe caractere, se va afișa prima pereche din text, cu această proprietate.

Exemplul 1

cuvinte6.in

calcul calcule are care parcare corecte corectie
1

cuvinte6.out

3

Explicație

Cerința 1:
Textul conține 3 perechi de cuvinte : (calcul,calcule), (are,care), (care,parcare).

Exemplul 2

cuvinte6.in

calcul calcule are care parcare corecte corectie
2

cuvinte6.out

corecte corectie

Explicație

Cerința 2: Perechea de cuvinte corecte corectie conține 14 caractere și reprezintă perechea cu cele mai multe caractere din text.