{"trustable":false,"sections":[{"title":"","value":{"format":"HTML","content":"\u003cp\u003e\r\n\tText-processing tools like \u003ci\u003e\u003cspan data-scayt_word\u003d\"awk\" data-scaytid\u003d\"1\"\u003eawk\u003c/span\u003e\u003c/i\u003e and \u003ci\u003e\u003cspan data-scayt_word\u003d\"sed\" data-scaytid\u003d\"2\"\u003esed\u003c/span\u003e\u003c/i\u003e allow you to automatically perform a sequence of editing operations based on a \u003cspan data-scayt_word\u003d\"script\" data-scaytid\u003d\"3\"\u003escript\u003c/span\u003e. For this problem we consider the specific case in which we want to perform a series of string replacements, within a single line of text, based on a fixed set of rules. Each rule specifies the string to find, and the string to replace it with, as shown below.\u003c/p\u003e\r\n\u003cblockquote\u003e\r\n\t\u003ctable\u003e\r\n\t\t\u003ctbody\u003e\r\n\t\t\t\u003ctr\u003e\r\n\t\t\t\t\u003ctd\u003e\r\n\t\t\t\t\tRule\u003c/td\u003e\r\n\t\t\t\t\u003ctd\u003e\r\n\t\t\t\t\tFind\u003c/td\u003e\r\n\t\t\t\t\u003ctd\u003e\r\n\t\t\t\t\tReplace-by\u003c/td\u003e\r\n\t\t\t\u003c/tr\u003e\r\n\t\t\t\u003ctr\u003e\r\n\t\t\t\t\u003ctd align\u003d\"RIGHT\"\u003e\r\n\t\t\t\t\t1.\u003c/td\u003e\r\n\t\t\t\t\u003ctd\u003e\r\n\t\t\t\t\t\u003ctt\u003eban \u003c/tt\u003e\u003c/td\u003e\r\n\t\t\t\t\u003ctd\u003e\r\n\t\t\t\t\t\u003ctt\u003e\u003cspan data-scayt_word\u003d\"bab\" data-scaytid\u003d\"4\"\u003ebab\u003c/span\u003e\u003c/tt\u003e\u003c/td\u003e\r\n\t\t\t\u003c/tr\u003e\r\n\t\t\t\u003ctr\u003e\r\n\t\t\t\t\u003ctd align\u003d\"RIGHT\"\u003e\r\n\t\t\t\t\t2.\u003c/td\u003e\r\n\t\t\t\t\u003ctd\u003e\r\n\t\t\t\t\t\u003ctt\u003e\u003cspan data-scayt_word\u003d\"baba\" data-scaytid\u003d\"5\"\u003ebaba\u003c/span\u003e \u003c/tt\u003e\u003c/td\u003e\r\n\t\t\t\t\u003ctd\u003e\r\n\t\t\t\t\t\u003ctt\u003ebe\u003c/tt\u003e\u003c/td\u003e\r\n\t\t\t\u003c/tr\u003e\r\n\t\t\t\u003ctr\u003e\r\n\t\t\t\t\u003ctd align\u003d\"RIGHT\"\u003e\r\n\t\t\t\t\t3.\u003c/td\u003e\r\n\t\t\t\t\u003ctd\u003e\r\n\t\t\t\t\t\u003ctt\u003e\u003cspan data-scayt_word\u003d\"ana\" data-scaytid\u003d\"6\"\u003eana\u003c/span\u003e \u003c/tt\u003e\u003c/td\u003e\r\n\t\t\t\t\u003ctd\u003e\r\n\t\t\t\t\t\u003ctt\u003eany\u003c/tt\u003e\u003c/td\u003e\r\n\t\t\t\u003c/tr\u003e\r\n\t\t\t\u003ctr\u003e\r\n\t\t\t\t\u003ctd align\u003d\"RIGHT\"\u003e\r\n\t\t\t\t\t4.\u003c/td\u003e\r\n\t\t\t\t\u003ctd\u003e\r\n\t\t\t\t\t\u003ctt\u003e\u003cspan data-scayt_word\u003d\"ba\" data-scaytid\u003d\"7\"\u003eba\u003c/span\u003e b \u003c/tt\u003e\u003c/td\u003e\r\n\t\t\t\t\u003ctd\u003e\r\n\t\t\t\t\t\u003ctt\u003ehind the g\u003c/tt\u003e\u003c/td\u003e\r\n\t\t\t\u003c/tr\u003e\r\n\t\t\u003c/tbody\u003e\r\n\t\u003c/table\u003e\r\n\u003c/blockquote\u003e\r\n\u003cp\u003e\r\n\tTo perform the edits for a given line of text, start with the first rule. Replace the first occurrence of the \u003ci\u003efind\u003c/i\u003e string within the text by the \u003ci\u003ereplace-by\u003c/i\u003e string, then try to perform the same replacement \u003cem\u003eagain\u003c/em\u003e on the new text. Continue until the \u003ci\u003efind\u003c/i\u003e string no longer occurs within the text, and then move on to the next rule. Continue until all the rules have been considered. Note that (1) when searching for a \u003ci\u003efind\u003c/i\u003e string, you always start searching at the beginning of the text, (2) once you have finished using a rule (because the \u003ci\u003efind\u003c/i\u003e string no longer occurs) you never use that rule again, and (3) case is significant.\u003c/p\u003e\r\n\u003cp\u003e\r\n\tFor example, suppose we start with the line\u003c/p\u003e\r\n\u003cblockquote\u003e\r\n\t\u003cspan style\u003d\"font-size:20px;\"\u003e\u003ctt\u003ebanana boat\u003c/tt\u003e\u003c/span\u003e\u003c/blockquote\u003e\r\n\u003cp\u003e\r\n\tand apply these rules. The sequence of transformations is shown below, where occurrences of a \u003ci\u003efind\u003c/i\u003e string are underlined and replacements are boldfaced. Note that rule 1 was used twice, then rule 2 was used once, then rule 3 was used zero times, and then rule 4 was used once.\u003c/p\u003e\r\n\u003cblockquote\u003e\r\n\t\u003ctable\u003e\r\n\t\t\u003ctbody\u003e\r\n\t\t\t\u003ctr\u003e\r\n\t\t\t\t\u003ctd\u003e\r\n\t\t\t\t\t\u0026nbsp;\u003c/td\u003e\r\n\t\t\t\t\u003ctd\u003e\r\n\t\t\t\t\tBefore\u003c/td\u003e\r\n\t\t\t\t\u003ctd\u003e\r\n\t\t\t\t\tAfter\u003c/td\u003e\r\n\t\t\t\u003c/tr\u003e\r\n\t\t\t\u003ctr\u003e\r\n\t\t\t\t\u003ctd\u003e\r\n\t\t\t\t\t\u0026nbsp;\u003c/td\u003e\r\n\t\t\t\t\u003ctd\u003e\r\n\t\t\t\t\t\u003ctt\u003e\u003cu\u003eban\u003c/u\u003eana boat \u003c/tt\u003e\u003c/td\u003e\r\n\t\t\t\t\u003ctd\u003e\r\n\t\t\t\t\t\u003ctt\u003e\u003cb\u003ebab\u003c/b\u003eana boat\u003c/tt\u003e\u003c/td\u003e\r\n\t\t\t\u003c/tr\u003e\r\n\t\t\t\u003ctr\u003e\r\n\t\t\t\t\u003ctd\u003e\r\n\t\t\t\t\t\u0026nbsp;\u003c/td\u003e\r\n\t\t\t\t\u003ctd\u003e\r\n\t\t\t\t\t\u003ctt\u003eba\u003cu\u003eban\u003c/u\u003ea boat \u003c/tt\u003e\u003c/td\u003e\r\n\t\t\t\t\u003ctd\u003e\r\n\t\t\t\t\t\u003ctt\u003eba\u003cb\u003ebab\u003c/b\u003ea boat\u003c/tt\u003e\u003c/td\u003e\r\n\t\t\t\u003c/tr\u003e\r\n\t\t\t\u003ctr\u003e\r\n\t\t\t\t\u003ctd\u003e\r\n\t\t\t\t\t\u0026nbsp;\u003c/td\u003e\r\n\t\t\t\t\u003ctd\u003e\r\n\t\t\t\t\t\u003ctt\u003e\u003cu\u003ebaba\u003c/u\u003eba boat \u003c/tt\u003e\u003c/td\u003e\r\n\t\t\t\t\u003ctd\u003e\r\n\t\t\t\t\t\u003ctt\u003e\u003cb\u003ebe\u003c/b\u003eba boat\u003c/tt\u003e\u003c/td\u003e\r\n\t\t\t\u003c/tr\u003e\r\n\t\t\t\u003ctr\u003e\r\n\t\t\t\t\u003ctd\u003e\r\n\t\t\t\t\t\u0026nbsp;\u003c/td\u003e\r\n\t\t\t\t\u003ctd\u003e\r\n\t\t\t\t\t\u003ctt\u003ebe\u003cu\u003eba\u003c/u\u003e\u003cu\u003e b\u003c/u\u003eoat \u003c/tt\u003e\u003c/td\u003e\r\n\t\t\t\t\u003ctd\u003e\r\n\t\t\t\t\t\u003ctt\u003ebe\u003cb\u003ehind the g\u003c/b\u003eoat\u003c/tt\u003e\u003c/td\u003e\r\n\t\t\t\u003c/tr\u003e\r\n\t\t\u003c/tbody\u003e\r\n\t\u003c/table\u003e\r\n\u003c/blockquote\u003e"}},{"title":"Input","value":{"format":"HTML","content":"\u003cp\u003e\r\n\tThe input contains one or more test cases, followed by a line containing only 0 (zero) that signals the end of the file. Each test case begins with a line containing the number of rules, which will be between 1 and 10. Each rule is specified by a pair of lines, where the first line is the\u0026nbsp;\u003ci\u003efind\u003c/i\u003e\u0026nbsp;string and the second line is the\u0026nbsp;\u003ci\u003ereplace-by\u003c/i\u003e\u0026nbsp;string. Following all the rules is a line containing the text to edit.\u0026nbsp;\u003c/p\u003e"}},{"title":"Output","value":{"format":"HTML","content":"\u003cp\u003e\r\n\tFor each test case, output a line containing the final edited text.\u003c/p\u003e\r\n\u003cp\u003e\r\n\tBoth\u0026nbsp;\u003ci\u003efind\u003c/i\u003e\u0026nbsp;and\u0026nbsp;\u003ci\u003ereplace-by\u003c/i\u003e\u0026nbsp;strings will be at most 80 characters long.\u0026nbsp;\u003ci\u003eFind\u003c/i\u003e\u0026nbsp;strings will contain at least one character, but\u0026nbsp;\u003ci\u003ereplace-by\u003c/i\u003e\u0026nbsp;strings may be empty (indicated in the input file by an empty line). During the edit process the text may grow as large as 255 characters, but the final output text will be less than 80 characters long.\u003c/p\u003e"}},{"title":"Sample Input","value":{"format":"HTML","content":"\u003cpre\u003e\r\n4\r\nban\r\n\u003cspan data-scayt_word\u003d\"bab\" data-scaytid\u003d\"8\"\u003ebab\u003c/span\u003e\r\n\u003cspan data-scayt_word\u003d\"baba\" data-scaytid\u003d\"9\"\u003ebaba\u003c/span\u003e\r\nbe\r\n\u003cspan data-scayt_word\u003d\"ana\" data-scaytid\u003d\"10\"\u003eana\u003c/span\u003e\r\nany\r\n\u003cspan data-scayt_word\u003d\"ba\" data-scaytid\u003d\"11\"\u003eba\u003c/span\u003e b\r\nhind the g\r\nbanana boat\r\n1\r\nt\r\n\u003cspan data-scayt_word\u003d\"sh\" data-scaytid\u003d\"12\"\u003esh\u003c/span\u003e\r\ntoe or top\r\n0\u003c/pre\u003e"}},{"title":"Sample Output","value":{"format":"HTML","content":"\u003cpre\u003e\r\nbehind the goat\r\nshoe or shop\u003c/pre\u003e"}},{"title":"Hint","value":{"format":"HTML","content":"\u003cp align\u003d\"left\"\u003e\r\n\twhen u read a line of string after an\u0026nbsp;\u003cspan data-scayt_word\u003d\"int\" data-scaytid\u003d\"17\"\u003eint\u003c/span\u003e, u can use following codes, like\u003c/p\u003e\r\n\u003cp align\u003d\"left\" style\u003d\"margin-left:37.4pt;\"\u003e\r\n\t\u003cspan data-scayt_word\u003d\"scanf\" data-scaytid\u003d\"18\"\u003escanf\u003c/span\u003e(\u0026quot;%d\u0026quot;,\u0026amp;t);getchar();gets(str);\u003c/p\u003e\r\n\u003cp align\u003d\"left\"\u003e\r\n\t\u003cstrong\u003eor u may read some unexpected words\u003c/strong\u003e\u003c/p\u003e"}}]}