Recherche de préfixe

Vous disposez d’un dictionnaire qui est initialement vide. Vous devez traiter une série de requêtes, chacune appartenant à l’un des deux types suivants :

1. Requête de type 1 : Ajouter un mot au dictionnaire.

   • Input: 1 word (1 ≤ |word| ≤ 1000), where word is a non-empty string consisting of lowercase English letters.

   • Action: Add the word to the dictionary.

2. Requête de type 2 : Compter le nombre de mots commençant par un préfixe donné.

   • Input: 2 prefix (1 ≤ |prefix| ≤ 1000), where prefix is a non-empty string consisting of lowercase English letters.

   • Output: Output the number of words in the dictionary that start with the given prefix.

- Entrée : 2 prefix (1 ≤ |prefix| ≤ 1000), où prefix est une chaîne non vide composée de lettres minuscules anglaises.

Entrée

La première ligne de l’entrée contient un entier n (1 ≤ n ≤ 100 000), correspondant au nombre de requêtes.

Les n lignes suivantes décrivent les requêtes. Chaque ligne est dans l’un des formats suivants :

• 1 word pour une requête de type 1.

• 2 prefix pour une requête de type 2.

Il est garanti que le nombre total de caractères dans l’entrée ne dépasse pas .

Sortie

Pour chaque requête de type 2, vous devez afficher sur une nouvelle ligne le nombre de mots du dictionnaire qui commencent par le préfixe donné.

Exemples