Präfixsuche

Sie haben ein Wörterbuch, das anfangs keine Einträge enthält. Nun sollen Sie eine Reihe von Abfragen bearbeiten, die in eine von zwei Kategorien fallen:

1. Abfragetyp 1: Ein Wort zum Wörterbuch hinzufügen.

   • 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. Abfragetyp 2: Zählen, wie viele Wörter mit einem bestimmten Präfix beginnen.

   • 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.

- Eingabe: 2 prefix (1 ≤ |prefix| ≤ 1000), wobei prefix ein nichtleerer String aus Kleinbuchstaben (Englisch) ist.

Eingabe

In der ersten Zeile der Eingabe steht eine ganze Zahl n (1 ≤ n ≤ 100 000), die die Anzahl der Abfragen angibt.

In den folgenden n Zeilen befinden sich die Abfragen, jeweils entweder:

• 1 word für eine Abfrage vom Typ 1.

• 2 prefix für eine Abfrage vom Typ 2.

Es ist sichergestellt, dass die Gesamtzahl der Zeichen in der Eingabe nicht überschreitet.

Ausgabe

Für jede Abfrage vom Typ 2 geben Sie in einer neuen Zeile eine ganze Zahl aus, die die Anzahl der Wörter im Wörterbuch angibt, die mit dem eingegebenen Präfix beginnen.

Beispiele