Պրեֆիքսային որոնում

Ձեզ տրվում է բառարան (dictionary), որը նախապես դատարկ է: Դուք պետք է մշակեք մի շարք հարցումներ, որոնք բաժանվում են երկու տարբեր տիպի.

1. Տիպ 1 հարցում: Բառ ավելացնել բառարան

   • 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. Տիպ 2 հարցում: Հաշվել, թե քանի բառ է սկսվում տրված պրեֆիքսով

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

- Մուտք: 2 prefix (1 ≤ |prefix| ≤ 1000), որտեղ prefix-ը նույնպես դատարկ չէ և բաղկացած է անգլերեն փոքրատառ տառերից

Μուտք

Մուտքի առաջին տողում տրված է մեկ ամբողջ թիվ n (1 ≤ n ≤ 100 000), որը ցույց է տալիս հարցումների քանակը:

Հաջորդ n տողերում տրված են հարցումները, և յուրաքանչյուր տող գալիս է հետևյալ ձևերից մեկով.

• 1 word (Տիպ 1 հարցում)

• 2 prefix (Տիպ 2 հարցում)

Երաշխավորված է, որ մուտքում ընդհանուր սիմվոլների քանակը չի գերազանցում -ը:

Ելք

Յուրաքանչյուր Տիպ 2 հարցման համար պետք է տպել մեկ ամբողջ թիվ առանձին տողում, որը ցույց է տալիս, թե քանի բառ է սկսվում տվյալ պրեֆիքսով:

Օրինակներ