Պրեֆիքսային տվյալների շտեմարան (Prefix Based Database)
Սկզբում դուք ունեք դատարկ տվյալների շտեմարան, որի վրա պետք է կատարեք որոշ հարցումներ։ Հարցումների երկու տեսակ կա՝ "Add" և "Search"։ "Add" հարցումը տվյալների շտեմարան է ավելացնում որոշակի անուն (name), իսկ "Search" հարցումը պահանջում է ցուցադրել բոլոր այն անունները, որոնք սկսվում են տրված պրեֆիքսով (prefix), դասավորված լեքսիկոգրաֆիկ կարգով։ Այնուամենայնիվ, եթե տվյալ պրեֆիքսին համապատասխանողները 20-ից ավել են, պետք է ցուցադրեք միայն առաջին 20-ը։
Մուտք
Մուտքի առաջին տողում տրված է ամբողջ թիվ
q (1 ≤ q ≤ 200 000), որը հարցումների քանակն է։ Հաջորդ q տողերում տրված են հարցումները հետևյալ ձևաչափով.- "Add" հարցումների դեպքում:
add s(որտեղs-ը այն անունն է, որը պետք է ավելացնել շտեմարան)
- "Search" հարցումների դեպքում:
search p(որտեղp-ը այն պրեֆիքսն է, որով պետք է որոնել)
Հարցման տողերի երկարությունը չի անցնում 20 նիշը։
Ելք
Յուրաքանչյուր "Search" հարցման համար պետք է տպել շտեմարանում պահվող այն անունները, որոնք սկսվում են տրված պրեֆիքսով, բաժանված մեկ սպեյսով։ Եթե պրեֆիքսին բավարարող անունները 20-ից ավել են, տպեք միայն առաջին 20-ը։
Օրինակ
Մուտք | Ելք |
9
add cat
add code
add core
search co
add profound
add found
search fo
add fight
search f | code
core
found
fight
found |
Constraints
Time limit: 6 seconds
Memory limit: 512 MB
Output limit: 15 MB