Xây dựng danh bạ


Submit solution

Points: 4 (partial)
Time limit: 1.0s
Memory limit: 977M

Author:
Problem types
Allowed languages
Ada, Assembly, Awk, C, C++, C11, CLANG, CLANGX, Classical, COBOL, Coffee, CSC, D lang, DART, F95, FORTH, Fortrn, GAS32, GO, Haskell, Itercal, Java, kotlin, LEAN, LISP, LUA, MONOVB, Nasm, OCAML, Pascal, Perl, php, PIKE, prolog, Pypy, Python, Ruby 2, RUST, Scala, SCM, SED, SWIFT, TCL, TUR, V8JS, VB, ZIG

Tichpx muốn xây dựng danh bạ liên lạc để lưu vào trong máy tính. Trong quá trình xây dựng danh bạ Tichpx để ý và thấy rằng rất nhiều từ nọ là tiền tố của từ kia. Nếu từ x được ghép bởi hai từ y và z tức là x=yz thì y được gọi là tiền tố và z gọi là hậu tố của x (Ví dụ từ tichpx có các tiền tố t, ti, tic, tich, tichp, tichpx). Trong khi cập nhật danh bạ với mỗi từ Tichpx có 1 trong hai thao tác

  • add là bổ sung một liên lạc vào danh bạ
  • find là tìm xem một từ là tiền tố của bao nhiêu liên lạc đã có

Bạn hãy lập trình để xác định giúp Tichpx nhé

Input

Dòng đầu chứa số nguyên dương n là số thao tác \((1<= n <= 10^5)\)

n dòng tiếp theo mỗi dòng thuộc một trong hai thao tác hoặc là add hoặc là find một liên lạc là một xâu gồm toàn chữ thường tiếng anh có độ dài không quá 30 ký tự

Output

Với mỗi thao tác find xuất ra màn hình số liên lạc đã có trong danh bạ có tiền tố muốn tìm

Ví dụ

Input

6
add daihocgiaothongvantai
add daihocthuyloi
find daihoc
add daihocxaydung
find hocvien
find dai

Output

2
0
3
tichpx

Comments

There are no comments at the moment.