{"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\u003eZayin have learned how to compute the number of periods of a string recently.\u003c/p\u003e\u003cp\u003eAs his girlfriend, Ziyin would like to give Zayin some strings and test whether he really learn the knowledge well. But Ziyin is too lazy to produce strings which are completely different, so she would firstly give Zayin a string, and ask him if she modify the $$$i$$$-th character of the string to \u003cspan class\u003d\"tex-font-style-tt\"\u003e#\u003c/span\u003e, what is the number of periods of the new string. (Note that Ziyin wouldn\u0027t really perform the modification)\u003c/p\u003e\u003cp\u003eIt\u0027s really a big question for Zayin. Can you help him so that he would not lose face in front of his girlfriend?\u003c/p\u003e"}},{"title":"Input","value":{"format":"HTML","content":"\u003cp\u003eThe first line contains a string $$$s$$$ ($$$1\\le|s|\\le 10^6$$$), which only contains lowercase letters.\u003c/p\u003e\u003cp\u003eThe second line contains an integer $$$q$$$ ($$$1\\le q\\le 10^6$$$), indicating the number of queries.\u003c/p\u003e\u003cp\u003eEach of the next $$$q$$$ lines contains an integer $$$i\\ (1\\le i\\le |s|)$$$, indicating Ziyin would modify the $$$i$$$-th character of the string to \u003cspan class\u003d\"tex-font-style-tt\"\u003e#\u003c/span\u003e.\u003c/p\u003e"}},{"title":"Output","value":{"format":"HTML","content":"\u003cp\u003eFor each of the $$$q$$$ queries, print an integer indicating the number of periods of the new string after Ziyin\u0027s modification.\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\u003eccpc\n4\n1\n2\n3\n4\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e0\n1\n1\n0\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}},{"title":"Note","value":{"format":"HTML","content":"\u003cp\u003eA integer number $$$T$$$ is a period of a string $$$s$$$ if and only if $$$1\\le T\u0026lt;|s|$$$ and $$$s[i]\u003ds[i-T]$$$ for every $$$i\\in\\big(T,|s|\\big]$$$.\u003c/p\u003e"}}]}