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

一次事件的描述如下:

• 一张脸出现在墙壁上, 说道:"有所改变, 我就让你看见新的道路." 于是$π$酱将牌组中的第 $x$ 张牌上的数字变化为 $y$ .

一场战斗的进行过程如下:

• 初始时卡组的 $n$ 张牌按 $1 \sim n$ 的顺序排列在抽牌堆中. 手牌和弃牌堆初始为空.
• 一次抽牌指将抽牌堆顶的一张牌放入手牌. 若抽牌时抽牌时抽牌堆为空, 则先进行一次洗牌, 即将弃牌堆中所有牌按 $1 \sim n$ 的顺序排列在抽牌堆中, 之后再将抽牌堆顶的牌放入手牌. 特别地, 若此时弃牌堆中也没有牌, 则认为此次抽牌不生效 (但仍然触发了洗牌).
  战斗过程进行若干个回合, 每一回合如下进行:
  • 我方回合开始, 进行 $m$ 次抽牌.
  • 打出若干张手牌, 每打出一张牌, 先执行该牌的效果 (进行 $a_i$ 次抽牌) ,再将该牌弃入弃牌堆.
  • 我方回合结束, 将所有手牌弃入弃牌堆. (不考虑敌方回合).
• $π$ 酱拥有技能"华丽牧场", 将在每次触发洗牌时对敌方造成大量伤害. 一场战斗在敌方死亡时结束.

$π$ 酱计划爬 $q$ 层塔, 即交替进行 $q$ 次换牌事件和 $q$ 场战斗. 由于每场战斗敌方的血量很高, $π$ 酱希望在某回合可以无限使用华丽牧场技能, 从而无限出伤消灭敌方, 且由于敌方每回合都会对他造成伤害, 他希望这个无限出伤的回合尽量早.

你的任务是帮助 $π$ 酱计算并回答在这 $q$ 场战斗中, 他最早能达到无限出伤的回合数分别是多少, 或告诉他这不可能(即使不可能无限出伤战斗也会正常结束, 不会影响接下来的战斗).

每个测试点包含多组测试数据, 第一行包含一个正整数 $t(t≤10^3 )$ , 表示测试数据的组数, 下面是每组测试数据的描述:

第一行包含两个正整数 $n(n≤10^5), m(m≤n)$, 分别表示卡组大小和每回合开始时的抽牌数.

第二行包括 $n$ 个非负整数, 第 $i$ 个数 $a_i (a_i≤n)$ 表示卡组第 $i$ 张牌上的数字.

第三行包含一个正整数 $q(q≤10^5)$ , 表示 $π$ 酱计划爬 $q$ 层塔.

接下来 $q$ 行每行两个整数 $x(1≤x≤n),y(0≤y≤n)$表示每层房间中变牌事件中变化的牌编号和变化后的数字.

保证$∑n≤5×10^5 ,∑q≤5×10^5$ , 最大的 $n,q $ 满足 $n,q≤10^5$ .

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