In this assignment, we will continue to add text searching to your arsenal. We continue using point of in$-$ terest $($POI$)$ search as the background application to minimise context switching. However, the algorithms you will implement are generic to text search problems and serve as fundamental building blocks of search engines such as Google or Bing. If you have missed Assignment $1,$ you can still compete this assignment $$ it would be helpful to revisit the first two pages of the Assignment $1$ specification to understand the context in this case. In Assignment $1,$ we have assumed that all POIs given are relevant to the queries $($e$.$g$.,$ they are all cafes$),$ and we only need to filter them based on the POI locations which are numeric properties. In reality, there are POIs of many different categories in the same area, and only few are relevant to a query. See Figure $1$ for example. There are not only cafes in the Melbourne CBD but also shops, supermarkets, hotels, post offices, a cathedral, etc. When a user queries for $$cafes$,$ none of the POIs in the other categories need to be considered. In this assignment, we will implement an algorithm to quickly filter out POIs of irrelevant categories $($or web documents in search engines, users in social network searches, etc.$).$ Figure $1$: POIs of different categories in Melbourne CBD $13$ Your Task The input POI and query dataset in this assignment is expanded to include POI category information. The input still contains two sections, with a sample input shown below: $1.$ At least $1$ and up to $50$ lines of POI records. Each line represents a POI, which starts with an unique integer POI ID of up to two digits $($the POI IDs are just the line numbers, to simplify the assignment$).$ Each POI record then contains two real numbers representing the POI coordinates in the x$-$ and y$-$ dimensions. After that, each POI record contains at least $1$ and up to $5$ category keywords $($category$$ for short hereafter$)$ separated by single whitespace characters. Each category is a string of at least $1$ and up to $20$ lower$-$case English letters. At the end of each line, there is a special character $$#$$ to indicate the end of the line $$ this is used to simplify input processing for the assignment; it is not part