Mots composés

La mère de Stofl est une souris très occupée. Elle est cadre d'une entreprise de production de fromage, c'est pourquoi elle doit souvent participer à des rencontres et discussions importantes, au cours desquelles de nombreuses expressions produisant un effet important et imposant sont utilisées.

Stofl ne comprend que rarement ce que ces expressions veulent dire et il a commencé à les analyser. Il a remarqué que tous ces termes sont composés de deux parties, d'un début de mot et d'une fin de mot. Il connaît maintenant la liste exacte de tous les débuts et fins de mots. Il aimerait donc savoir combien de termes différents ils peut former en les associant. Note que les deux parties sont acollées et ne peuvent pas se superposer, même si le début et la fin de mot sont identiques.

Tâche

Deux listes de mots sont données, l'une avec les débuts de mots et l'autre avec les fins de mots. Calcule le nombre de mots différents que l'on peut obtenir en combinant les débuts avec les fins de mots. Si un même mot est obtenu avec des combinaisons différentes, il ne faut le compter qu'une fois. Prends note du fait que la tâche est sensible à la casse, c'est-à-dire qu'une lettre minuscule est considérée comme différente de la lettre majuscule correspondante. 'debutfin' et 'debutFin' sont donc différents.

Entrée

La première ligne contient un entier $A$ – le nombre de mots dans la liste des débuts de mots.

Les $A$ lignes suivantes contiennent chacune une suite de lettres de l'alphabet anglais ('A' à 'Z' et 'a' à 'z').

La ligne $A+2$ contient un entier $B$ – le nombre de mots dans la liste des fins de mots.

Les $B$ lignes suivantes contiennent chacune une suite de lettres de l'alphabet anglais ('A' à 'Z' et 'a' à 'z').

Tu peux considérer que les mots ne contiendront pas plus de $L$ caractères ($L$ est donné ci-dessous, section 'Limites').

Sortie

Ta sortie doit contenir un entier – le nombre de mots différents obtenus en combinant les débuts et fins de mots comme décrit ci-dessus.

Limites

  • Pour les cas valant 40% des points, $1 \le A, B \le 100$ et $L \le 10$.
  • Pour les cas valant 90% des points, $1 \le A, B \le 10\,000$ et $L \le 15$.
  • Pour les cas valant 100% des points, $1 \le A, B \le 50\,000$ et $L \le 100$.

Exemple 1

InputOutput

2
Geld
Geldau
2
tomaten
automaten

3

On peut former les mots Geldtomaten, Geldautomaten et Geldauautomaten (Geldautomaten peut être formé de deux façons différentes).

Exemple 2

InputOutput

6
Organisations
Identifikations
Drittgenerations
Koalitions
Fluktuations
Wachstums
9
struktur
ebene
tendenz
programmierung
konzeption
phase
kritik
problematik
kontingenz

54

Envoi