Imagine you are working for a search engine company called Ikroch. People do a lot of spelling mistakes when searching in your search engine. So you need to develop a program which corrects user’s queries. In this problem, for each test case you are given a list of dictionary words and their corresponding weights and a lot of queries. Each query is a line which consists of a search input qi followed by an integer X. The search input qi of the query is composed of a list of space separated lowercase words. For each query, correct all words of the search input by the following rules.
2/2 Output For each test case, print the case number in a single line. Then for each query you have to print a line containing search input corrected by Ikroch. Consecutive words of corrected search input should be separated by a single space (if corrected search input contains more than one word). Notes: • Explanation of 1st test case: Ikroch Distance (wird, weird) = 1 Ikroch Distance (wird, wired) = 1 But because weird has a higher weight than wired thus output will be weird. The word ‘problem’ is located inside the dictionary so this is just returned. • Explanation of 2nd test case: No word is found for ‘its’ within 1 Ikroch Distance so skipped. Both hard and herd have 1 Ikroch Distance with ‘heard’. Both answers have same weight, thus hard is returned as it’s lexicographically smallest. Ikroch Distance (wether, weather) = 1 Ikroch Distance (wether, whether) = 1 But because ‘weather’ has a higher weight than ‘whether’ thus output will be ‘weather’. Sample Input 2 42 weird 3 wired 2 problemo 5 problem 2 wird problem 1 wird problemo 0 61 hard 1 herd 1 today 2 itt 3 weather 4 whether 1 its heard wether tday 1 Sample Output Case 1: weird problem problemo Case 2: hard weather today