给定一个长度为 的环形数组 ，具体而言，我们可以认为 的最后一个数字 的下一个数字为 的第一个数字 。 初始时，鼠标的光标指向数组的第 个数字 ，接下来，光标将进行 次跃迁，每次跃迁将使光标向后一次性移动 个元素，随后将该位置的元素累加进得分中（初始时得分为 ）。 正如你猜的那样，旺仔哥哥想问你光标完成 次跃迁后，最终的总得分是多少。由于这个答案可能很大，你只需要输出这个结果对 取模的结果即可。 由于旺仔哥哥非常有良心，所以会进行 次这样的提问，每次都给出一组新的 和 ，你都需要回答出对应情况下的结果。

输入描述:

第一行输入三个整数 ，表示环形数组的长度、每次跃迁将使光标向后一次性移动的元素个数、旺仔哥哥询问的次数。第二行输入 个整数 ，表示数组中各个元素的值。此后  行，第 行输入两个整数 ，表示第 次询问的起点、跃迁次数。

输出描述:

对于每一次询问，新起一行输出一个整数，表示该次询问的答案对 取模的结果。

备注:

本题已于下方时间节点更新，请注意题解时效性：1. 2025-11-19 优化题面文本与格式，修复输入描述中变量 重复使用的问题；新增一组样例。原 std 有误，修正并更新数据。