最中间的数

Problem Description

小 E 在玩一个打擂台的游戏。 参与游戏的共有 $n$ 位选手（保证 $n$ 为奇数），每位选手都有两个参数：

• 位置 $v_i$，一个在 $[1,10^6]$ 内的整数，表示选手 $i$ 所处位置。保证任意时刻没有选手位置重叠。
• 能力 $c_i$，表示选手 $i$ 的能力值。选手的能力值固定不变。保证任意两个选手能力值不同。 这个游戏的规则为：
• 游戏只有唯一的胜者。
• 游戏进行 $n-1\over 2$ 轮，每轮选出最左侧的三个未淘汰选手上擂台（即 $v_i$ 最小的三个）。
• 每轮擂台的胜出者为三个人按能力值排序后，处于中间的选手。此时擂台的胜出者位置固定不变，另外两个选手淘汰。
• 最后唯一一位没有被淘汰的选手为冠军。 小 E 可能会有若干参数的修改，故会有如下两种操作：
• 修改：1 x y 表示将选手 $x$ 的位置改到 $y$，保证不与其他选手当前位置重叠。
• 询问：2 要求输出按照当前站位，游戏的胜者的编号。

Input

本题有多组测试数据。第一行一个正整数 $T$，表示数据组数，接下来输入每组测试数据。 对于每组测试数据：

• 第一行两个正整数 $n,m$，表示选手个数和操作数。
• 第二行 $n$ 个正整数 $v_i$，表示选手的初始位置。
• 第三行 $n$ 个正整数 $c_i$，表示选手的能力值。
• 接下来 $m$ 行，为以下两种形式之一：
• 1 x y，表示一次修改操作。
• 2，表示一次询问操作。

Output

对每组测试的每个询问操作，输出一个正整数表示胜者编号。

Sample Input

1
5 7
3 1 4 2 5
1 2 3 4 5
2
1 1 17
2
1 1 3
1 4 123
1 3 2
2

Sample Output

3
3
4

Hint

对于所有数据 $1\leq T\leq 5$，且：

• $3\leq n\leq 5\times 10^5$。保证 $n$ 为奇数。
• $1\leq m\leq 5\times 10^5$。
• $1\leq v_i, y\leq 10^6$。保证任意时刻任意两个选手位置不重合。
• $1\leq c_i\leq 10^6$。保证任意两个选手能力值不同。
• $1\leq x\leq n$。

Source

2025“钉耙编程”中国大学生算法设计暑期联赛（8）