Un cuvânt se numește k-ps dacă prefixul său de lungime k este identic cu sufixul de lungime k, iar k este cea mai mare valoare strict mai mică decât lungimea cuvântului, cu această proprietate. Dacă nu există nicio astfel de valoare k nenulă, spunem despre cuvânt că este 0-ps. De exemplu, amalgam este 2-ps, iar amestec este 0-ps.

Cerința

Rezolvați următoarele cerințe:

1) Se dă un cuvânt. Determinați k asfel încât cuvântul să fie k-ps.
2) Se dă un șir de caractere în care cuvintele sunt alcătuite din litere mici ale alfabetului englez și sunt separate prin spații. Să se afișeze în ordine cuvintele 0-ps, 1-ps, 2-ps, 3-ps, etc, până la cel mai mare k pentru care există în șir cel puțin un cuvânt k-ps. Pentru fiecare categorie, cuvintele vor fi afișate în ordine alfabetică.

Date de intrare

Fișierul de intrare kps.in conține pe prima linie numărul C, care reprezintă cerința și poate fi 1 sau 2.

• Dacă C=1, a doua linie conține un cuvânt format litere mici ale alfabetului englez.
• daca C=2, a doua linie conține șir de caractere în care cuvintele sunt alcătuite din litere mici ale alfabetului englez și sunt separate prin spații.

Date de ieșire

• Dacă C=1, fișierul de ieșire kps.out va conține pe prima linie numărul K, astel încât cuvântul dat este cuvânt K-ps. Dacă cuvântul dat nu este cuvânt k-ps, se va afișa valoarea 0.
• Dacă C=2, fișierul de ieșire kps.out va conține mai multe linii:
  • prima linie corespunde cuvintelor 0-ps, a doua corespunde cuvintelor 1-ps, a treia cuvintelor 2-ps, etc.
  • fiecare linie începe cu numărul de cuvinte din categoria curentă, urmat de un spațiu și de aceste cuvinte, in ordine alfabetică, separate prin câte un spațiu;
  • dacă nu există niciun cuvânt dintr-o anumită categorie, linia corespunzătoare va conține doar valoarea 0.

Restricții și precizări

• pentru C=1, cuvântul dat va avea cel mult 1000 de litere;
• pentru C=2, șirul dat va avea cel mult 10000 de caractere, fiecare cuvânt având cel mult 100 de litere;
• pentru 50 de puncte, C=1.

Exemplul 1

kps.in

1
amalgam

kps.out

2

Exemplul 2

kps.in

2
asdfqwasdf zar amalgam  zarzar  barbar ghjtttyuttghj asaswasas kps

kps.out

2 kps zar
0
1 amalgam
3 barbar ghjtttyuttghj zarzar
2 asaswasas asdfqwasdf