{"trustable":true,"sections":[{"title":"","value":{"format":"MD","content":"\u003cp\u003eChefland scientists have made a new invention! They developed a new way to represent a string with \u003cb\u003eN\u003c/b\u003e symbols: consider a tree with \u003cb\u003eN\u003c/b\u003e vertices, rooted at the first vertice. For each vertice, a single latin letter is written. So we have obtained a \"\u003cb\u003etreestring\u003c/b\u003e\". The scientists haven\u0027t decided yet how the treestring should be pronounced, but they have invented a definition of a \u003cb\u003esubstring for a treestring\u003c/b\u003e. A string is a \u003cb\u003esubstring of a treestring\u003c/b\u003e if and only it can be obtained by moving from some vertice to its descendant and writing out all the letters from vertices that occured on this path in the order they have appeared. For example, consider the following treestring :\r\n\u003cbr\u003e\u003cbr\u003e\r\n\u003cimg src\u003d\"CDN_BASE_URL/cde020cb0cb7f4d8af1ab76c3cf8c0f7?v\u003d1716008432\" /\u003e\r\n\u003cbr\u003e\r\nThe string \"ba\" is a \u003cb\u003esubstring\u003c/b\u003e of a given treestring because it can be obtained by moving from vertice \u003cb\u003e4\u003c/b\u003e to vertice \u003cb\u003e6\u003c/b\u003e, the string \"abb\" is also a substring of this treestring - it can be obtained by moving from the root to vertice \u003cb\u003e5\u003c/b\u003e. However the string \"cb\" is \u003cb\u003enot a substring\u003c/b\u003e of this treestring because there is no way from any vertice to its descendant in such a way that the sequence of letters is \"cb\".\r\n\u003cbr\u003e\u003cbr\u003e\r\nNow the Chefland researchers ask you to help them with the treestring research. \r\nThey have given you a treestring with \u003cb\u003eN\u003c/b\u003e vertices. \r\nPlease output the number of \u003cb\u003edistinct\u003c/b\u003e substrings of a given treestring (including the empty one). \r\nThen, \u003cb\u003eQ\u003c/b\u003e queries will follow. \r\nFor the \u003cb\u003ei\u003c/b\u003e-th query, the permutation \u003cb\u003eP\u003csub\u003ei\u003c/sub\u003e\u003c/b\u003e of \u003cb\u003e26\u003c/b\u003e latin alphabet letters and an integer \u003cb\u003eK\u003csub\u003ei\u003c/sub\u003e\u003c/b\u003e will be given.\r\nThat means that if we sort all distinct substrings of the given treestring according to the \u003cb\u003ealphabetical order described in P\u003csub\u003ei\u003c/sub\u003e\u003c/b\u003e, you will have to output the \u003cb\u003eK\u003csub\u003ei\u003c/sub\u003e\u003c/b\u003e-th string.\r\n\"According to the alphabetical order described in \u003cb\u003eP\u003csub\u003ei\u003c/sub\u003e\u003c/b\u003e\" means that letter \u003cb\u003eX\u003c/b\u003e is lexicographically smaller that letter \u003cb\u003eY\u003c/b\u003e if and only \u003cb\u003eX\u003c/b\u003e appears\r\nin \u003cb\u003eP\u003csub\u003ei\u003c/sub\u003e\u003c/b\u003e earlier than \u003cb\u003eY\u003c/b\u003e. For example if the \u003cb\u003ealphabetical order\u003c/b\u003e is \"cbadefghijklmnopqrstuvwxyz\", then letter \"c\" is \u003cb\u003elexicographically smaller\u003c/b\u003e than letter \"a\" because \"c\" is the first symbol of this permutation, and \"a\" is the third symbol of this permutation, therefore 1\u003c3 and for the given arrangement, \"c\" is \u003cb\u003ealphabetically less\u003c/b\u003e than \"a\".\r\nHere note that the string \u003cb\u003eA\u003c/b\u003e is smaller than the string \u003cb\u003eB\u003c/b\u003e (that means \u003cb\u003eA\u003c/b\u003e comes earlier than \u003cb\u003eB\u003c/b\u003e\r\nafter sorting) if and only if\r\n\u003cb\u003eA\u003c/b\u003e is a prefix of \u003cb\u003eB\u003c/b\u003e,\r\nor \u003cb\u003eA\u003csub\u003ei\u003c/sub\u003e\u003c/b\u003e \u003d \u003cb\u003eB\u003csub\u003ei\u003c/sub\u003e\u003c/b\u003e (for all \u003cb\u003ei\u003c/b\u003e \u003c \u003cb\u003ek\u003c/b\u003e) and \u003cb\u003eA\u003csub\u003ek\u003c/sub\u003e\u003c/b\u003e \u003c \u003cb\u003eB\u003csub\u003ek\u003c/sub\u003e\u003c/b\u003e (in terms of alphabetical order)\r\nwhere \u003cb\u003eA\u003csub\u003ei\u003c/sub\u003e\u003c/b\u003e denotes the \u003cb\u003ei\u003c/b\u003e-th letter of \u003cb\u003eA\u003c/b\u003e.\r\n\r\n\u003ch3\u003eConstraints\u003c/h3\u003e\r\n\u003cp\u003e\u003cul\u003e\r\n\u003cli\u003e1\u003c\u003d\u003cb\u003eN\u003c/b\u003e\u003c\u003d250000\u003c/li\u003e\r\n\u003cli\u003e1\u003c\u003d\u003cb\u003eQ\u003c/b\u003e\u003c\u003d50000\u003c/li\u003e\r\n\u003cli\u003e1\u003c\u003d\u003cb\u003eK\u003csub\u003ei\u003c/sub\u003e\u003c/b\u003e\u003c\u003d9223372036854775807 (2^63-1)\u003c/li\u003e\r\n\u003cli\u003eOutput will not exceed 800 KB.\u003c/li\u003e\r\n\u003cli\u003eIt is guaranteed that the N lowercase latin letters have been generated randomly.\u003c/li\u003e\r\n\u003c/ul\u003e\u003cbr\u003e\r\n\r\n\u003ch3\u003eInput\u003c/h3\u003e\r\n\u003cp\u003eThe first line of input consists of two integers - \u003cb\u003eN\u003c/b\u003e and \u003cb\u003eQ\u003c/b\u003e.\u003cbr\u003eThen, a string composed of \u003cb\u003eN\u003c/b\u003e lowercase latin letters follow.\u003cbr\u003e\r\nThen, \u003cb\u003eN-1\u003c/b\u003e lines follow. Each line is composed of \u003cb\u003etwo\u003c/b\u003e numbers - \u003cb\u003eX\u003csub\u003ei\u003c/sub\u003e\u003c/b\u003e and \u003cb\u003eY\u003csub\u003ei\u003c/sub\u003e\u003c/b\u003e. It means that there is an edge between vertice \u003cb\u003eX\u003csub\u003ei\u003c/sub\u003e\u003c/b\u003e and vertice \u003cb\u003eY\u003csub\u003ei\u003c/sub\u003e\u003c/b\u003e.\u003cbr\u003e\r\nThen, \u003cb\u003eQ\u003c/b\u003e lines follow. Each line consists of a permutation of \u003cb\u003e26\u003c/b\u003e lowercase latin letters \u003cb\u003eP\u003csub\u003ei\u003c/sub\u003e\u003c/b\u003e and an integer \u003cb\u003eK\u003csub\u003ei\u003c/sub\u003e\u003c/b\u003e.\r\n\r\n\u003ch3\u003eOutput\u003c/h3\u003e\r\n\u003cp\u003eOutput \u003cb\u003eQ+1\u003c/b\u003e lines. On the first line output a single integer - the number of \u003cb\u003edistinct\u003c/b\u003e substrings of a given treestring. The following \u003cb\u003eQ\u003c/b\u003e lines should contain answers to the queries. \u003cb\u003eI\u003c/b\u003e-th line should contain an answer to \u003cb\u003ei\u003c/b\u003e-th query or a string \u003cb\u003e\"-1\"\u003c/b\u003e if it is impossible\r\nto find \u003cb\u003eK\u003csub\u003ei\u003c/sub\u003e\u003c/b\u003e-th string for \u003cb\u003ei\u003c/b\u003e-th query.\r\n\r\n\u003ch3\u003eExample\u003c/h3\u003e\r\n\r\n\u003cpre\u003e\r\n\u003cb\u003eInput:\u003c/b\u003e\r\n8 4\r\nabcbbaca\r\n1 2\r\n2 3\r\n1 4\r\n4 5\r\n4 6\r\n4 7\r\n1 8\r\nabcdefghijklmnopqrstuvwxyz 5\r\nabcdefghijklmnopqrstuvwxyz 1\r\nbcadefghijklmnopqrstuvwxyz 5\r\nabcdefghijklmnopqrstuvwxyz 100\r\n\r\n\u003cb\u003eOutput:\u003c/b\u003e\r\n12\r\naba\r\n\r\nba\r\n-1\r\n\u003c/pre\u003e"}}]}