华丽牧场

Problem Description

$\pi$ 酱正在攀登一座尖塔, 通过尖塔的某层需要依次经过两个房间, 第一个房间会触发一次事件, 第二个房间会进行一场战斗. 刚进入尖塔的 $\pi$ 酱初始拥有一套卡组, 卡组包含 $n$ 张牌, 第 $i$ 张牌上写有数字 $a_i$ ($a_i\geq 0$), 表示打出这张牌会抽 $a_i$ 张牌. 一次事件的描述如下:

• 一张脸出现在墙壁上, 说道:"有所改变, 我就让你看见新的道路." 于是$\pi$酱将牌组中的第 $x$ 张牌上的数字变化为 $y$ . 一场战斗的进行过程如下:
• 初始时卡组的 $n$ 张牌按 $1\sim n$ 的顺序排列在抽牌堆中. 手牌和弃牌堆初始为空.
• 一次抽牌指将抽牌堆顶的一张牌放入手牌. 若抽牌时抽牌时抽牌堆为空, 则先进行一次洗牌, 即将弃牌堆中所有牌按 $1\sim n$ 的顺序排列在抽牌堆中, 之后再将抽牌堆顶的牌放入手牌. 特别地, 若此时弃牌堆中也没有牌, 则认为此次抽牌不生效 (但仍然触发了洗牌).
• 战斗过程进行若干个回合, 每一回合如下进行:
• 我方回合开始, 进行 $m$ 次抽牌.
• 打出若干张手牌, 每打出一张牌, 先执行该牌的效果 (进行 $a_i$ 次抽牌) ,再将该牌弃入弃牌堆.
• 我方回合结束, 将所有手牌弃入弃牌堆. (不考虑敌方回合).
• $\pi$ 酱拥有技能"华丽牧场", 将在每次触发洗牌时对敌方造成大量伤害. 一场战斗在敌方死亡时结束. $\pi$ 酱计划爬 $q$ 层塔, 即交替进行 $q$ 次换牌事件和 $q$ 场战斗. 由于每场战斗敌方的血量很高, $\pi$ 酱希望在某回合可以无限使用华丽牧场技能, 从而无限出伤消灭敌方, 且由于敌方每回合都会对他造成伤害, 他希望这个无限出伤的回合尽量早. 你的任务是帮助 $\pi$ 酱计算并回答在这 $q$ 场战斗中, 他最早能达到无限出伤的回合数分别是多少, 或告诉他这不可能(即使不可能无限出伤战斗也会正常结束, 不会影响接下来的战斗).

Input

每个测试点包含多组测试数据, 第一行包含一个正整数 $t$($t\leq 10^3$) , 表示测试数据的组数, 下面是每组测试数据的描述: 第一行包含两个正整数 $n$($n\leq 10^5$) , $m$($m\leq n$), 分别表示卡组大小和每回合开始时的抽牌数. 第二行包括 $n$ 个非负整数, 第 $i$ 个数 $a_i$($a_i\leq n$) 表示卡组第 $i$ 张牌上的数字. 第三行包含一个正整数 $q$($q\leq 10^5$) , 表示 $\pi$ 酱计划爬 $q$ 层塔. 接下来 $q$ 行每行两个整数 $x$($1\leq x\leq n$), $y$($0\leq y\leq n$)表示每层房间中变牌事件中变化的牌编号和变化后的数字. 保证$\sum n\leq 5\times 10^5$, $\sum q\leq 5\times 10^5$, 最大的 $n$, $q$ 满足 $n, q\leq 10^5$.

Output

$q$ 行, 第 $i$ 行表示第 $i$ 个房间中进行的战斗最小的能够无限出伤的回合数, 如果没有这样的回合输出-1.

Sample Input

2
10 5
0 0 0 0 3 0 0 0 0 3
3
10 2
5 4
1 1
10 5
0 0 0 0 0 0 0 0 0 0
2
1 10
2 1

Sample Output

-1
2
1
-1
1

Source

2024“钉耙编程”中国大学生算法设计超级联赛（7）