{"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\u003eJB is the National Olympiad Tutor of Suffix Automaton. Today he comes up with the following problem.\u003c/p\u003e\u003cp\u003eSuppose you have a string $$$S$$$, we write down all the distinct substrings in $$$S$$$. Then we sort the strings according to their length in increasing order. For two strings with the same length, the one that has the smaller lexicographical order comes first. Now we have a sorted string sequence $$$A$$$.\u003c/p\u003e\u003cp\u003eJB has $$$Q$$$ questions, for each question, he will give you one integer $$$k$$$ and suppose you to tell him the $$$k$$$-th string in $$$A$$$.\u003c/p\u003e\u003cp\u003eTo simplify the problem, you just need to tell him the left and right positions in $$$S$$$ of the first occurrence of the string.\u003c/p\u003e"}},{"title":"Input","value":{"format":"HTML","content":"\u003cp\u003eThe first line contains one string $$$S$$$ ($$$1\\leq |S|\\leq 10^6$$$), containing only lowercase letters.\u003c/p\u003e\u003cp\u003eThe second line contains one integer $$$Q$$$ ($$$1\\leq Q\\leq 10^6$$$).\u003c/p\u003e\u003cp\u003eThe following $$$Q$$$ lines describe the questions, each of which contains one integer $$$k$$$ ($$$1\\leq k\\leq 10^{12}$$$).\u003c/p\u003e"}},{"title":"Output","value":{"format":"HTML","content":"\u003cp\u003eFor each question, print two integers $$$l, r$$$, denoting the left and right positions in $$$S$$$ of the first occurrence of the answer string. If $$$k$$$ is greater than the length of $$$A$$$, just print \"\u003cspan class\u003d\"tex-font-style-tt\"\u003e-1 -1\u003c/span\u003e\".\u003c/p\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\u003eccpcguilin\n5\n1\n10\n4\n8\n26\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e1 1\n2 3\n8 8\n1 2\n4 7\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}},{"title":"","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\u003ebanana\n3\n5\n10\n16\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e1 2\n2 5\n-1 -1\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}}]}