Fişierul intrare/ieşire:	cuvinte5.in, cuvinte5.out	Sursă	Summer Challenge 2019
Autor	Alexandru Petrescu	Adăugată de	Theodor Moroianu •theodor.moroianu
Timp execuţie pe test	0.2 sec	Limită de memorie	256000 kbytes
Scorul tău	N/A	Dificultate	N/A

Vezi solutiile trimise | Statistici

Cuvinte5

Se defineste diferenta intre doua cuvinte ca fiind patratul numarului minim de adaugari, stergeri sau modificari de caractere necesare pentru a transforma un cuvant in celalalt.
De exemplu, pentru a il transforma pe 'abc' in 'ba' in 2 astfel de modificari, putem face 'abc' -> 'bc' -> 'ba', deci diferenta dintre cele doua cuvinte este 2² = 4.

Se considera un dictionar. Distanta intre doua cuvinte A si B, care nu apartin neaparat dictionarului, cu parametrul suplimentar K, se defineste ca fiind cea mai mica suma a diferentelor intre cuvintele consecutive ale unui sir de maxim K + 1 cuvinte, intre care primul este A, ultimul este B, iar restul cuvintelor apartin dictionarului.

Sa presupunem ca in dictionar avem doar cuvintele lavera, lauera si lalala. Atunci distanta intre cuvintele laverita si laura, cand K = 3, se obtine transformand laverita in lavera, lavera in lauera si lauera in laura. Atunci cand K = 2, in schimb, distanta va fi mai mare, pentru ca vom transforma laverita in lavera si lavera in laura.

Cerinta

Se da un dictionar de N cuvinte si Q queryuri de forma K A B. Pentru fiecare query, se cere sa aflati distanta de la cuvantul A la cuvantul B, cu parametrul suplimentar K.

Date de intrare

Prima linie contine N, numarul de cuvinte din dictionar.
A doua linie contine cele N cuvinte, despartite printr-un spatiu.

A treia linie contine Q, numarul de queryuri.
Urmatoarele Q linii contin cate un query, dat sub forma K A B.

Date de ieşire

Pentru fiecare query se afiseaza cate o linie cu raspunsul.

Restricţii

• 1 ≤ N ≤ 50
• 1 ≤ Q ≤ 2.500
• 1 ≤ Lungimea Cuvintelor ≤ 7
• 1 ≤ K ≤ N + 1
• Cuvintele sunt formate din litere mici ale alfabetului latin.
• Pentru teste in valoare de 20p queryurile nu contin decat cuvinte din dictionar (testele 1, 2, 3, 4).
• Pentru alte teste in valoare de 20p K = N + 1 (testele 5, 6, 7, 8).
• Pentru alte teste in valoare de 10p 1 ≤ Q ≤ 50 (testele 9, 10).

Exemplu

Explicaţie

Pentru primul query, putem face 'a' -> 'aaa' -> 'aaaa', costul este 4 + 1 = 5
Pentru al doilea query, putem face 'a' -> 'aa' -> 'aaa' -> 'aaaa', costul este 1 + 1 + 1 = 3
Pentru al treilea, putem face 'ab' -> 'aa' -> 'aaa' -> 'aaab' -> 'aaabb' -> 'aaabbb', costul este 1 + 1 + 1 + 1 + 1 = 5.
Pentru al patrulea, putem face 'ab' -> 'aaab' -> 'aaabb' -> 'aaabbb', costul este 2² + 1 + 1 = 6
Pentru al cincilea, putem face 'xxx' -> 'yyy', costul este 3^2 = 9
Pentru ultimul caz, putem face 'zz' -> 'aa' -> 'aaa' -> 'aaab' -> 'azab', costul este 2² + 1 + 1 + 1 = 7

Cum se trimit solutii?