{"trustable":true,"sections":[{"title":"","value":{"format":"HTML","content":"\u003cstyle type\u003d\"text/css\"\u003e .sampledata { font-family: \"Courier New\", Courier, monospace; white-space: pre; }\u003c/style\u003e\u003cp\u003e\u0026nbsp;阿狸喜欢收藏各种稀奇古怪的东西,最近他淘到一台老式的打字机。打字机上只有28个按键,分别印有26个小写英文字母和\u0027B\u0027、\u0027P\u0027两个字母。\u003cbr\u003e \u003cbr\u003e 经阿狸研究发现,这个打字机是这样工作的:\u003cbr\u003e \u003cbr\u003e l 输入小写字母,打字机的一个凹槽中会加入这个字母(这个字母加在凹槽的最后)。\u003cbr\u003e \u003cbr\u003e l 按一下印有\u0027B\u0027的按键,打字机凹槽中最后一个字母会消失。\u003cbr\u003e \u003cbr\u003e l 按一下印有\u0027P\u0027的按键,打字机会在纸上打印出凹槽中现有的所有字母并换行,但凹槽中的字母不会消失。\u003cbr\u003e \u003cbr\u003e 例如,阿狸输入aPaPBbP,纸上被打印的字符如下:\u003cbr\u003e \u003cbr\u003e a\u003cbr\u003e \u003cbr\u003e aa\u003cbr\u003e \u003cbr\u003e ab\u003cbr\u003e \u003cbr\u003e 我们把纸上打印出来的字符串从1开始顺序编号,一直到n。打字机有一个非常有趣的功能,在打字机中暗藏一个带数字的小键盘,在小键盘上输入两个数(x,y)(其中1≤x,y≤n),打字机会显示第x个打印的字符串在第y个打印的字符串中出现了多少次。\u003cbr\u003e \u003cbr\u003e 阿狸发现了这个功能以后很兴奋,他想写个程序完成同样的功能,你能帮助他么?\u003c/p\u003e"}},{"title":"Input","value":{"format":"HTML","content":"\u003cp\u003e\u0026nbsp;输入的第一行包含一个字符串,按阿狸的输入顺序给出所有阿狸输入的字符。\u003cbr\u003e \u003cbr\u003e 第二行包含一个整数m,表示询问个数。\u003cbr\u003e \u003cbr\u003e 接下来m行描述所有由小键盘输入的询问。其中第i行包含两个整数x, y,表示第i个询问为(x, y)。\u003c/p\u003e"}},{"title":"Output","value":{"format":"HTML","content":"\u003cp\u003e\u0026nbsp;输出m行,其中第i行包含一个整数,表示第i个询问的答案。\u003c/p\u003e"}},{"title":"Sample Input","value":{"format":"HTML","content":"\u003cspan class\u003dsampledata\u003eaPaPBbP\r\n\r\n3\r\n\r\n1 2\r\n\r\n1 3\r\n\r\n2 3\r\n\r\n\u003c/span\u003e\u003c/div\u003e"}},{"title":"Sample Output","value":{"format":"HTML","content":"\u003cspan class\u003dsampledata\u003e2\r\n\r\n1\r\n\r\n0\u003c/span\u003e\u003c/div\u003e"}},{"title":"Hint","value":{"format":"HTML","content":"\u003cp\u003e\u003c/p\u003e\n\u003cp\u003e\u0026nbsp;1\u0026lt;\u003dN\u0026lt;\u003d10^5\u003c/p\u003e\n\u003cbr\u003e \n\u003cdiv\u003e\n 1\u0026lt;\u003dM\u0026lt;\u003d10^5\n\u003c/div\u003e\n\u003cbr\u003e \n\u003cdiv\u003e\n 输入总长\u0026lt;\u003d10^5\n\u003c/div\u003e\n\u003cp\u003e\u003c/p\u003e"}}]}