Algorithms and Data Structures

Prefix Search

You are given a dictionary that initially contains no words. You need to process a series of queries, each falling into one of two types:
  1. Type 1 query: Add a word to the dictionary.
      • 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.
  1. Type 2 query: Count the number of words starting with a given prefix.
      • 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.
You need to implement a program that processes these queries efficiently.

Input

The first line of the input contains a single integer, n (1 ≤ n ≤ 100 000), representing the number of queries.
The following n lines contain the queries. Each line is in one of the following formats:
  • 1 word for a Type 1 query.
  • 2 prefix for a Type 2 query.
It is guaranteed that the total number of characters in the input does not exceed .

Output

For each Type 2 query, output a single integer on a new line representing the number of words in the dictionary that start with the given prefix.

Examples

Input
Output
7 1 aba 1 abac 1 caba 2 ab 1 caba 1 cd 2 c
2 3

Constraints

Time limit: 3.5 seconds

Memory limit: 512 MB

Output limit: 1 MB

To check your solution you need to sign in
Sign in to continue