{"trustable":true,"sections":[{"title":"","value":{"format":"MD","content":"\u003ch3\u003e Read problems statements in \u003ca target\u003d\"_blank\" href\u003d\"https://www.codechef.com/download/translated/SNCKFL16/mandarin/BEAUTY.pdf\"\u003eMandarin Chinese\u003c/a\u003e, \u003ca target\u003d\"_blank\" href\u003d\"https://www.codechef.com/download/translated/SNCKFL16/russian/BEAUTY.pdf\"\u003eRussian\u003c/a\u003e and \u003ca target\u003d\"_blank\" href\u003d\"https://www.codechef.com/download/translated/SNCKFL16/vietnamese/BEAUTY.pdf\"\u003eVietnamese\u003c/a\u003e as well.\u003c/h3\u003e\r\n\r\n\r\n\u003cp\u003e\r\nChef is going to participate in \u0027Who will prepare the most beautiful sandwich?\u0027 reality show. The show requires participants to prepare sandwiches that not only look beautiful, but taste delicious too. The show also releases a list of ingredients that you are allowed to use in the sandwich. This time, the list consists of \u003cb\u003eK\u003c/b\u003e ingredients. For the purpose of our problem, you can assume that each ingredient is denoted by a lower case Latin character. So the first \u003cb\u003eK\u003c/b\u003e lower case Latin letters will describe all the ingredients.\u003c/p\u003e\r\n\r\n\u003cp\u003e\r\nChef\u0027s sandwich consists of \u003cb\u003eN\u003c/b\u003e parts of ingredients packed in a row. You can think of it as a string of length \u003cb\u003eN\u003c/b\u003e containing the first \u003cb\u003eK\u003c/b\u003e English letters only.\u003c/p\u003e\r\n\r\n\u003cp\u003e\r\nChef thinks the beauty of the sandwich is an integer that can be computed in the following way: \r\n\u003cul\u003e\r\n\u003cli\u003eFirst partition the sandwich into consecutive blocks of maximal length such that all the parts in the same block are of same ingredient.\u003c/li\u003e\r\n\u003cli\u003eBeauty of this sandwich is the sum of squared lengths of the blocks.\u003c/li\u003e\r\n\u003c/ul\u003e\r\n\u003c/p\u003e\r\n\r\n\u003cp\u003e\r\nFor example, let the sandwich be denoted by \"aadddbabb\".\r\n\r\n\u003cul\u003e\r\n\u003cli\u003eChef partitions it in this way - aa, ddd, b, a, bb\u003c/li\u003e\r\n\u003cli\u003eBeauty of this sandwich is equal to 2*2 + 3*3 + 1*1 + 1*1 + 2*2 \u003d 19\u003c/li\u003e\r\n\u003c/ul\u003e\r\n\u003c/p\u003e\r\n\r\n\u003cp\u003e\r\nThere will be \u003cb\u003eQ\u003c/b\u003e judges in the show. Chef diligently worked for days in preparing \u003cb\u003eQ\u003c/b\u003e such sandwiches before the show. Now, it is the show time. He just got an information from the back stage anchor that some of the judges are allergic to some ingredients. Now, Chef has to sit down and take out each sandwich and remove all the ingredients that the judge (the one who is supposed to taste it) is allergic to. After doing that, he will rearrange the parts of the sandwich continuously without leaving any ugly looking gap. \r\n\u003c/p\u003e\r\n\r\n\u003cp\u003e\r\nNow, Chef is worrying about the beauty of the sandwiches presented to various judges. He asks you to help in this.\r\n\u003c/p\u003e\r\n\r\n\u003ch3\u003eInput\u003c/h3\u003e\r\n\u003cp\u003eThe first line of the input contains two space separated integers \u003cb\u003eN\u003c/b\u003e and \u003cb\u003eK\u003c/b\u003e, denoting the number of parts in the sandwich and the number of available ingredients, respectively.\u003c/p\u003e\r\n\u003cp\u003eThe second line contains a string of length \u003cb\u003eN\u003c/b\u003e having only the first \u003cb\u003eK\u003c/b\u003e Latin lower case letters, denoting the sandwich.\u003c/p\u003e\r\n\u003cp\u003eThe third line contains a single integer \u003cb\u003eQ\u003c/b\u003e, denoting the number of judges.\u003c/p\u003e\r\n\u003cp\u003eEach of the following \u003cb\u003eQ\u003c/b\u003e lines contains a string denoting the ingredients to which the corresponding judge is allergic. The string will be sorted in ascending order of their characters. No character will appear more than once in it.\u003c/p\u003e\r\n\r\n\u003ch3\u003eOutput\u003c/h3\u003e\r\n\u003cp\u003eFor each query, output a single integer in a separate line denoting the beauty of the sandwich that the corresponding judge will be tasting.\u003c/p\u003e\r\n\r\n\u003ch3\u003eConstraints\u003c/h3\u003e\r\n\u003cli\u003e\u003cb\u003e1\u003c/b\u003e ≤ \u003cb\u003eN\u003c/b\u003e ≤ \u003cb\u003e200,000\u003c/b\u003e\u003c/li\u003e\r\n\u003cli\u003e\u003cb\u003e1\u003c/b\u003e ≤ \u003cb\u003eK\u003c/b\u003e ≤ \u003cb\u003e18\u003c/b\u003e\u003c/li\u003e\r\n\u003cli\u003e\u003cb\u003e1\u003c/b\u003e ≤ \u003cb\u003eQ\u003c/b\u003e ≤ \u003cb\u003e262,143\u003c/b\u003e\u003c/li\u003e\r\n\u003c/ul\u003e\r\n\r\n\u003ch3\u003eExample\u003c/h3\u003e\r\n\u003cpre\u003e\u003cb\u003eInput:\u003c/b\u003e\r\n\u003ctt\u003e7 4\r\nacabada\r\n2\r\nb\r\nac\r\n\u003c/tt\u003e\r\n\u003cb\u003eOutput:\u003c/b\u003e\r\n\u003ctt\u003e8\r\n2\u003c/tt\u003e\r\n\u003c/pre\u003e\r\n\r\n\u003ch3\u003eExplanation\u003c/h3\u003e\r\n\u003cp\u003e\u003cb\u003eFirst\u003c/b\u003e judge is allergic to ingredient denoted by \u0027b\u0027. So Chef has to remove this ingredient from the judge\u0027s sandwich. After that, the sandwich will be \"acaada\". Its beauty will be 1*1 + 1*1 + 2*2 + 1*1 + 1*1 \u003d 8\r\n\u003c/p\u003e\r\n\r\n\u003cp\u003e\u003cb\u003eSecond\u003c/b\u003e judge is allergic to ingredients denoted by characters \u0027a\u0027 and \u0027c\u0027. After removing these ingredients, the sandwich will become \"bd\" and its beauty will be 2.\r\n\u003c/p\u003e\r\n\u003c/p\u003e"}}]}