{"trustable":true,"prependHtml":"\u003cstyle type\u003d\u0027text/css\u0027\u003e\n .input, .output {\n border: 1px solid #888888;\n }\n .output {\n margin-bottom: 1em;\n position: relative;\n top: -1px;\n }\n .output pre, .input pre {\n background-color: #EFEFEF;\n line-height: 1.25em;\n margin: 0;\n padding: 0.25em;\n }\n \u003c/style\u003e\n \u003clink rel\u003d\"stylesheet\" href\u003d\"//codeforces.org/s/96598/css/problem-statement.css\" type\u003d\"text/css\" /\u003e\n\u003cscript\u003e\n window.katexOptions \u003d {\n delimiters: [\n {left: \u0027$$$$$$\u0027, right: \u0027$$$$$$\u0027, display: true},\n {left: \u0027$$$\u0027, right: \u0027$$$\u0027, display: false},\n {left: \u0027$$\u0027, right: \u0027$$\u0027, display: true},\n {left: \u0027$\u0027, right: \u0027$\u0027, display: false}\n ]\n };\n\u003c/script\u003e\n","sections":[{"title":"","value":{"format":"HTML","content":"\u003cp\u003ePolycarp is working on a new operating system called BerOS. He asks you to help with implementation of a file suggestion feature.\u003c/p\u003e\u003cp\u003eThere are $$$n$$$ files on hard drive and their names are $$$f_1, f_2, \\dots, f_n$$$. Any file name contains between $$$1$$$ and $$$8$$$ characters, inclusive. All file names are unique.\u003c/p\u003e\u003cp\u003eThe file suggestion feature handles queries, each represented by a string $$$s$$$. For each query $$$s$$$ it should count number of files containing $$$s$$$ as a substring (i.e. some continuous segment of characters in a file name equals $$$s$$$) and suggest any such file name.\u003c/p\u003e\u003cp\u003eFor example, if file names are \"\u003cspan class\u003d\"tex-font-style-tt\"\u003eread.me\u003c/span\u003e\", \"\u003cspan class\u003d\"tex-font-style-tt\"\u003ehosts\u003c/span\u003e\", \"\u003cspan class\u003d\"tex-font-style-tt\"\u003eops\u003c/span\u003e\", and \"\u003cspan class\u003d\"tex-font-style-tt\"\u003eberos.18\u003c/span\u003e\", and the query is \"\u003cspan class\u003d\"tex-font-style-tt\"\u003eos\u003c/span\u003e\", the number of matched files is $$$2$$$ (two file names contain \"\u003cspan class\u003d\"tex-font-style-tt\"\u003eos\u003c/span\u003e\" as a substring) and suggested file name can be either \"\u003cspan class\u003d\"tex-font-style-tt\"\u003ehosts\u003c/span\u003e\" or \"\u003cspan class\u003d\"tex-font-style-tt\"\u003eberos.18\u003c/span\u003e\".\u003c/p\u003e"}},{"title":"Input","value":{"format":"HTML","content":"\u003cp\u003eThe first line of the input contains integer $$$n$$$ ($$$1 \\le n \\le 10000$$$) — the total number of files.\u003c/p\u003e\u003cp\u003eThe following $$$n$$$ lines contain file names, one per line. The $$$i$$$-th line contains $$$f_i$$$ — the name of the $$$i$$$-th file. Each file name contains between $$$1$$$ and $$$8$$$ characters, inclusive. File names contain only lowercase Latin letters, digits and dot characters (\u0027\u003cspan class\u003d\"tex-font-style-tt\"\u003e.\u003c/span\u003e\u0027). Any sequence of valid characters can be a file name (for example, in BerOS \"\u003cspan class\u003d\"tex-font-style-tt\"\u003e.\u003c/span\u003e\", \"\u003cspan class\u003d\"tex-font-style-tt\"\u003e..\u003c/span\u003e\" and \"\u003cspan class\u003d\"tex-font-style-tt\"\u003e...\u003c/span\u003e\" are valid file names). All file names are unique.\u003c/p\u003e\u003cp\u003eThe following line contains integer $$$q$$$ ($$$1 \\le q \\le 50000$$$) — the total number of queries.\u003c/p\u003e\u003cp\u003eThe following $$$q$$$ lines contain queries $$$s_1, s_2, \\dots, s_q$$$, one per line. Each $$$s_j$$$ has length between $$$1$$$ and $$$8$$$ characters, inclusive. It contains only lowercase Latin letters, digits and dot characters (\u0027\u003cspan class\u003d\"tex-font-style-tt\"\u003e.\u003c/span\u003e\u0027).\u003c/p\u003e"}},{"title":"Output","value":{"format":"HTML","content":"\u003cp\u003ePrint $$$q$$$ lines, one per query. The $$$j$$$-th line should contain the response on the $$$j$$$-th query — two values $$$c_j$$$ and $$$t_j$$$, where\u003c/p\u003e\u003cul\u003e \u003cli\u003e $$$c_j$$$ is the number of matched files for the $$$j$$$-th query, \u003c/li\u003e\u003cli\u003e $$$t_j$$$ is the name of any file matched by the $$$j$$$-th query. If there is no such file, print a single character \u0027\u003cspan class\u003d\"tex-font-style-tt\"\u003e-\u003c/span\u003e\u0027 instead. If there are multiple matched files, print any. \u003c/li\u003e\u003c/ul\u003e"}},{"title":"Examples","value":{"format":"HTML","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e4\ntest\ncontests\ntest.\n.test\n6\nts\n.\nst.\n.test\ncontes.\nst\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e1 contests\n2 .test\n1 test.\n1 .test\n0 -\n4 test.\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}}]}