有一个长度为 的 环形字符串 ，具体而言，我们可以认为 的最后一个字符 的下一个字符为 的第一个字符 ，如图所示： 初始时，鼠标的光标指向 的第 个字符 ，接下来，光标将进行 次跃迁，假设跃迁前光标指向 的第 个字符 ，那么每次跃迁的规则如下： 若 后方 个字符（不含 ）中若存在 ，则直接跃迁到这些字符中最远的一个 的位置上。 否则，直接跃迁到 后方一个字符 （若 则跃迁到 处）上。 你需要求出，在经过这 次跃迁后，光标最终停在了 的第几个字符。由于出题人非常有良心，所以会进行 次这样的提问，每次都给出一组新的 和 ，你都需要回答出对应情况下的结果。

输入描述:

输入的第一行包含空格隔开的三个正整数 ，分别为环形字符串  的长度、单词跃迁时向后找零的最大长度以及询问的次数。第二行，一个长度为  的  字符串 （）。接下来  行，每行两个整数 （），表示起点在 ，移动  次。

输出描述:

输出  行，每行一个正整数，表示光标最终停下的位置。