{"trustable":true,"prependHtml":"\u003cstyle type\u003d\"text/css\"\u003e\n div.illustration {\n float: right;\n padding-left: 20px;\n }\n div.illustration .illustration {\n width: 100%;\n border-radius: 4px;\n }\n pre {\n display: block;\n margin: 0 0 10px;\n font-size: 13px;\n line-height: 1.42857143;\n color: #333;\n word-break: break-all;\n word-wrap: break-word;\n }\n\u003c/style\u003e\n\u003cscript\u003e\n window.katexOptions \u003d {\n delimiters: [\n {left: \u0027\\\\[\u0027, right: \u0027\\\\]\u0027, display: true}\n ]\n };\n\u003c/script\u003e\n","sections":[{"title":"","value":{"format":"HTML","content":"\n \u003cp\u003eSam is starting a new company, and has just chosen its name.\n The name is a string \u003cspan class\u003d\"tex2jax_process\"\u003e$s \u003d\n s_1s_2\\dots s_ n$\u003c/span\u003e of length \u003cspan class\u003d\"tex2jax_process\"\u003e$n$\u003c/span\u003e. The name is so long that\n customers won’t remember the full name. Rather, each customer\n is going to remember only a substring \u003cspan class\u003d\"tex2jax_process\"\u003e$t$\u003c/span\u003e of the full name, and different\n customers may remember different substrings.\u003c/p\u003e\n\n \u003cp\u003eSam is curious how memorable the substring \u003cspan class\u003d\"tex2jax_process\"\u003e$t$\u003c/span\u003e will be to a customer. Sam\n believes that the more palindromes \u003cspan class\u003d\"tex2jax_process\"\u003e$t$\u003c/span\u003e contains, the more memorable it\n is. Recall that a string \u003cspan class\u003d\"tex2jax_process\"\u003e$w$\u003c/span\u003e is a palindrome if \u003cspan class\u003d\"tex2jax_process\"\u003e$w$\u003c/span\u003e reads the same forwards and\n backwards (for example, the strings \u003ctt class\u003d\"ttfamily\"\u003eradar\u003c/tt\u003e and \u003ctt class\u003d\"ttfamily\"\u003elevel\u003c/tt\u003e are\n palindromes, while the string \u003ctt class\u003d\"ttfamily\"\u003eever\u003c/tt\u003e is\n not). After all, customers are sensitive to symmetries in the\n substring \u003cspan class\u003d\"tex2jax_process\"\u003e$t$\u003c/span\u003e that he or\n she remembers, and palindromes are full of symmetries. As such,\n Sam wants to find out the number of substrings \u003cspan class\u003d\"tex2jax_process\"\u003e$w$\u003c/span\u003e of \u003cspan class\u003d\"tex2jax_process\"\u003e$t$\u003c/span\u003e such that \u003cspan class\u003d\"tex2jax_process\"\u003e$w$\u003c/span\u003e is a palindrome.\u003c/p\u003e\n\n \u003cp\u003eThe challenge is that Sam’s company will have tons of\n customers. It is difficult for Sam to know how memorable his\n company name is to all these customers. Can you help Sam?\u003c/p\u003e\n\n \u003ch2\u003eInput\u003c/h2\u003e\n\n \u003cp\u003eThe first line of input contains a string \u003cspan class\u003d\"tex2jax_process\"\u003e$s \u003d s_1s_2 \\dots s_ n$\u003c/span\u003e consisting of\n \u003cspan class\u003d\"tex2jax_process\"\u003e$n$\u003c/span\u003e lowercase letters\n (\u003cspan class\u003d\"tex2jax_process\"\u003e$1 \\leq n \\leq 100\\,\n 000$\u003c/span\u003e). The second line contains an integer \u003cspan class\u003d\"tex2jax_process\"\u003e$m$\u003c/span\u003e (\u003cspan class\u003d\"tex2jax_process\"\u003e$1\n \\leq m \\leq 100\\, 000$\u003c/span\u003e), denoting the number of\n customers. Then \u003cspan class\u003d\"tex2jax_process\"\u003e$m$\u003c/span\u003e lines\n follow, each containing a pair of integers \u003cspan class\u003d\"tex2jax_process\"\u003e$\\ell $\u003c/span\u003e and \u003cspan class\u003d\"tex2jax_process\"\u003e$r$\u003c/span\u003e (\u003cspan class\u003d\"tex2jax_process\"\u003e$1\n \\leq \\ell \\leq r \\leq n$\u003c/span\u003e), indicating that a customer\n remembers precisely the substring \u003cspan class\u003d\"tex2jax_process\"\u003e$s_\\ell s_{\\ell +1} \\dots s_ r$\u003c/span\u003e\n between the \u003cspan class\u003d\"tex2jax_process\"\u003e$\\ell $\u003c/span\u003eth and\n \u003cspan class\u003d\"tex2jax_process\"\u003e$r$\u003c/span\u003eth characters\n inclusive.\u003c/p\u003e\n\n \u003ch2\u003eOutput\u003c/h2\u003e\n\n \u003cp\u003eFor each customer, output a line containing an integer that\n indicates how memorable the company name is to the customer.\n More specifically, if this customer remembers the substring\n \u003cspan class\u003d\"tex2jax_process\"\u003e$s_\\ell s_{\\ell +1} \\dots s_\n r$\u003c/span\u003e, output the number of pairs of indices \u003cspan class\u003d\"tex2jax_process\"\u003e$(i,j)$\u003c/span\u003e such that \u003cspan class\u003d\"tex2jax_process\"\u003e$\\ell \\leq i \\leq j \\leq r$\u003c/span\u003e and\n \u003cspan class\u003d\"tex2jax_process\"\u003e$s_ i s_{i+1} \\dots s_ j$\u003c/span\u003e\n is a palindrome.\u003c/p\u003e\n\n \u003ch2\u003eSample 1\u003c/h2\u003e\u003cbody\u003e\u003ctable class\u003d\"vjudge_sample\"\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\u003eaabacab\n5\n1 7\n1 4\n3 7\n2 5\n5 7\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e11\n6\n7\n5\n3\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n\u003c/body\u003e\n "}}]}