U204727 背单词

梁老师家的狗豆豆，记性不是很好。过年了，别人家的狗都会表演节目，让它坐下就坐下，让它握手就握手。但是豆豆什么都学不会，只会吃和睡。于是梁老师决定教它背单词，教给了它一个n个字母组成的单词，单词里面只有小写字母。但是它还是记不住，于是梁老师就让它不停重复写这个单词，写m遍。 比如有一个3个字母的单词dog，写5遍，就变成了 `dogdogdogdogdog`。这样一共有$n \times m$个字母，它们的位置分别从1编号到$n \times m$。 豆豆的好朋友小野猫（一只名字叫小野的猫）更笨，它连单词都不认识，它只认识字母。它问了豆豆q个问题，每个问题都是从第l个位置到第r个位置，包括这两个边界的位置，某个小写字母c出现了几次。豆豆的脑容量都用来记单词了，实在没时间帮小野算，请你帮助豆豆回答每个询问。

第一行输入三个整数n，m和q，表示单词的长度，重复写多少遍，以及有多少次询问。 接下来一行有一个长度为n的字符串，表示单词，全部由小写字母组成。 接下来有q行，每行两个数字l和r，以及一个小写字母c，表示要查询l到r位置中，c出现了多少次。

输出q行，每行一个数字，表示每个询问的答案。

样例解释，dog写5遍以后会变成`dogdogdogdogdog`，第一次询问1到4位置，是`dogd`，所以d出现了2次。 第2次询问3到4位置，是`gd`,所以o出现了0次。 第3次询问1到15位置，一共g出现了5次。 数据范围： $1 \le n,m,q \le 10^6$ $1 \le l \le r \le n*m$