Ikroch

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.

1. If the word is exactly found inside the dictionary don’t change the word.
2. Otherwise, if the word is within X Ikroch Distance with another word found in the dictionary, then replace the word with the dictionary word. If more than one word from the dictionary matches with the word then pick the word with the highest weight. If more than one words form dictionary has the same weight then lexicographically smallest word will be chosen.
3. If none of the above rules is applicable, delete the word from search input. Two words is within X Ikroch Distance, if using at most X of following operations, one word can be changed to another:
4. You can insert a character in any place in the word. 2. You can remove any character from the word. Like Ikroch Distance of ‘WA’ and ‘AC’ is 2 (Remove W and add C in last of ‘WA’). Ikroch Distance of ‘ABCD’ and ‘B’ is 3. Input Input starts with an integer T (≤ 10) denoting the number of test cases. Each test case starts with a line containing two integers dw (1 ≤ dw ≤ 4∗104) and q (1 ≤ q ≤ 105). dw denotes number of dictionary words and q denotes number of queries. Each of the next dw lines will contain a string of lowercase letters di (1 ≤ length of(di) ≤ 10) denoting a dictionary word and an integer wi (1 ≤ wi ≤ 103) denoting its weight. Each of the next q lines will contain multiple space separated lower case search input qw (1 ≤ length of(qw) ≤ 10) followed by an integer X (0 ≤ X ≤ 1). The length of each query line is not more than 50. Constraint for each test case: All characters will be in the range of [a-z] i=dw ∑ length of(di) ≤ 2 ∗ 105 i=1 i=qw ∑ length of(qi) ≤ 2 ∗ 105 i=1

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