几乎每天，这老虎都是饿肚子的。而每次饿肚子肚子都会咕咕叫。
小灰兔呢笑坏了就暗戳戳地听着，发现了一个规律——这笨老虎每天肚子都会叫n次，而这n次肚子又按轻响之分被小灰兔分成了A~Z等，听着听着它就觉得这是一种美妙的音乐。
于是小灰兔决定将这声音记录下来写成乐谱。不过小灰兔才学会拿笔，只会画方和画圆，于是一个等级的咕咕叫将会被小灰兔画成像下面一样的东西：

□□□○□

或者

□○

或者

□

总之就是圆方结合的东西。
可怜的是，小灰兔的白纸有限，所以它要尽可能少画圆方。
接下来就是问题所在了——

也许今天小灰兔会觉得第i天到第j天的咕咕叫特别好听，所以它打算从这些天中挑选连续的m天记录下来，而每次将A~Z怎么记录这个是由小灰兔自己当时定的。然后也许它明天又会觉得第k天到第l天的咕咕叫特别好听，而记录方案又是另一种。

所以对于小灰兔的每次心血来潮，你都需要给小灰兔找到一种方案——即将第几天到第几天的咕咕叫以怎么样的圆方记录下来使得圆方数最少。

举个例子，比如说这几天的咕咕叫是ABABAC，那么其中一种方案可以是设A为○，B为□○，C为□□，即

○□○○□○□□

总之方案数有无数种，你当然要给找出最好的那种。

本题有多组数据，每组数据第一行为三个整数T（1 <= T <= 100000，即总天数），N（1 <= N <= 50，为老虎每天肚子叫的次数）以及M（1 <= M <= 10，且M小于T，即每张乐谱所需的天数）。
接下来有一个长为N * T的字符串，仅含A~Z，代表老虎的咕咕叫。
接下去是一个整数Q(1 <= Q <= 50000，代表小灰兔心血来潮了Q次)。
然后接下去Q行，每行两个整数a和b(b > a 且 b - a > M)，代表这次小灰兔的乐谱将从a到b天中挑选。

对于小灰兔的每次心血来潮，你需要给它算出最少需要画几个圆方。