小C和小T准备金字塔探秘.他们建造了一个N层的金字塔,并把他们喜欢的句子写在上面,一行一行地重复(每行的方向相反,具体看示例). 就像下面的示例:

图片

小T选了K个问题,每个问题包含一个数字a和字母c,表示询问”在金字塔的第a行有多少个字母c出现”.你是小C的助手,请写一个程序帮助他解决问题!

第一行输入一个整数N(1<=N<=10^18),代表金字塔的高度. 第二行一个字符串表示他们喜欢的句子(全部是大写英语字母),句子的长度不超过10^6. 第三行一个整数K(1<=K<=50000),表示小T选择的问题个数. 接下来K行,包含一个数字a,字母c,表示小T的问题.