题目描述

一个环上按顺时针顺序排列着 $n$ 个位置，编号为 $1,2,\ldots,n$，其中位置 $n$ 与位置 1 相邻。位置 $i$ 上有一个非零整数 $a_i$。

每次游戏开始时，你可以任选一个位置作为起点，将该位置上的数加入总分，并拥有 $k$ 次剩余跳跃次数。

只要剩余跳跃次数大于 0，就必须从当前位置 $i$ 跳跃：

• 若 $a_i>0$，顺时针移动 $a_i$ 步；
• 若 $a_i<0$，逆时针移动 $|a_i|$ 步。

跳跃沿环进行，可以经过同一位置多次。每跳跃一次，剩余跳跃次数减少 1，并将落点上的数加入总分。跳跃途中经过的位置不计分。

你的朋友提出了 $q$ 次询问。每次询问指定一个特殊区域：从位置 $l$ 开始，顺时针连续的 $d$ 个位置。对于该次询问，每当一次跳跃从特殊区域外的位置出发、落在特殊区域内的位置时，剩余跳跃次数额外减少 1。起点位于特殊区域内不触发额外扣减，跳跃途中经过特殊区域也不触发额外扣减。

完成一次跳跃及其扣减后，如果剩余跳跃次数小于或等于 0，游戏立即结束。本次跳跃落点上的数仍计入总分。

对于每次询问，求游戏结束时可能获得的最大总分，以及有多少个不同起点可以获得该最大总分。各次询问互相独立，游戏开始时的剩余跳跃次数均为 $k$。

输入格式

从文件 circle.in 中读取数据。

第一行包含两个整数 $n,k$，分别表示环上的位置数和初始跳跃次数。

第二行包含 $n$ 个整数 $a_1,a_2,\ldots,a_n$。

第三行包含一个整数 $q$，表示询问次数。

接下来 $q$ 行，每行包含两个整数 $l,d$，表示特殊区域从位置 $l$ 开始，顺时针连续包含 $d$ 个位置。

输出格式

输出到文件 circle.out 中。

对于每次询问，输出一行两个整数，分别表示最大总分和能够获得该最大总分的起点数量。

样例

3 2
2 -1 1
2
3 1
1 2

4 1
5 1

4 2
5 5 5 5
1
2 2

15 3

数据规模与约定

本题采用子任务捆绑计分：只有通过一个子任务的全部测试点，才能获得该子任务的分数。

对于所有数据，满足：

• $1\le n\le2\times10^4$；
• $1\le k\le10^{10}$；
• $1\le q\le2\times10^2$；
• $-10^8\le a_i\le10^8$，且 $a_i\ne0$；
• 每次询问均满足 $1\le l\le n$，$1\le d\le n$。

下发文件

下载三组测试数据，非真实测试数据