Boğl

Boggle stolüstü oyununun böyük pərəstişkarı olduğunuzu düşünürəm. Əgər qaydaları bilmirsinizsə, narahat olmayın, mən sizə izah edəcəyəm. Boggle $4\times 4$ ölçüsündə bir hərf şəbəkəsindən ibarətdir və məqsəd mümkün qədər çox söz tapmaqdır. Həyat yoldaşımla Boggle oynayanda, o həmişə qalib gəlir və uduzan (yəni mən) ev işlərini görməli olur, məsələn, zibili atmaq. Mənə qalib gəlməyə kömək edin.

Boggle-da sözlər qonşu hərflərdən (üfüqi, şaquli və diaqonal) qurulur, lakin bir hüceyrə bir sözdə yalnız bir dəfə istifadə edilə bilər. Yalnız lüğətdə olan sözlər düzgün hesab olunur.

$3$ və ya $4$ hərfdən ibarət sözlər $1$ xal, $5$ hərfdən ibarət sözlər $2$ xal, $6$ hərfdən ibarət sözlər $3$ xal, $7$ hərfdən ibarət sözlər $5$ xal, $8$ hərfdən ibarət sözlər isə $11$ xal dəyərindədir. Əgər bir neçə söz tapsanız (ümid edirəm ki, belə olacaq), onların xalları cəmlənir.

Giriş verilənləri

Birinci sətir lüğətdəki sözlərin sayını $w(1<w<300000)$ göstərir. Sonrakı $w$ sətirin hər biri bir sözü ehtiva edir. Sözlər $8$ böyük hərfə qədər ('A' — 'Z') ibarətdir. Lüğət hissəsindən sonra boş bir sətir gəlir. Növbəti sətir Boggle lövhələrinin sayını $b(1<b<30)$ göstərir. Hər lövhə dörd sətirdə $4\times 4$ böyük hərf şəbəkəsindən ibarətdir. Boggle lövhələri arasında boş bir sətir var.

Çıxış verilənləri

Hər lövhə üçün mümkün olan maksimum xal cəmini, ən uzun sözü və tapılan sözlərin sayını çıxarın. Bir Boggle-da iki dəfə (və ya daha çox) rast gəlinən sözlər yalnız bir dəfə sayılır. Əgər bir neçə ən uzun söz varsa, leksik qrafik olaraq ən kiçiyini çıxarın. Hər Boggle-da ən azı bir düzgün söz olduğunu düşünün.

Nümunələr