首当其冲II

题目描述

Orange在玩一个卡牌游戏，双方轮流出牌，必须保证每一轮的卡牌都比对方点数大。同时，每个人的手牌都是有序的，假设你选择的第 $p$ 张牌是一张满足条件的牌，你要打出它，就会失去它前方的所有牌。双方谁先失去所有牌或者无法出牌，则会输掉游戏。

因此，为了尽量避免输掉游戏，假设对方出的牌点数为 $v$，Orange想要你找出在卡牌点数序列 $a[l,...,r]$ 中从左边开始第一张点数大于 $v$ 的牌的位置，如果不存在这样的牌，则输出-1。

此外，Orange可以对指定的牌进行重置，每次可以修改一个位置的牌，将他的点数替换成另外的点数，即 $a_p \leftarrow x$。

输入格式

输入包含多组测试数据，第一行为一个整数 $T$，表示测试数据组数。 对于每组测试数据： 第一行为两个整数 $n, m$，表示代表卡牌点数的序列 $a_i$ 和Orange的操作次数。 第二行为 $n$ 个整数，表示序列 $a_i$。 接下来 $m$ 行，每行行一条指令：

op x y (v)

若 $op = 1$，则表示查询 $x \sim y$ 之间从左边开始第一张点数大于 $v$ 的牌的位置。 若 $op = 2$，则表示将位置为 $x$ 的牌的点数替换成 $y$，即 $a_x \leftarrow y$。

数据范围

$1 \le n, m \le 10^5$ $1 \le a_i,v,x \le 10^9$ $1 \le l \le r \le n$ $\sum n,m \le 3\times 10^5$

输出格式

对于每条 $op=1$ 的指令，输出一个答案，占一行。

样例 #1

样例输入 #1

1
5 5
2 4 1 3 2
1 1 3 2
1 3 5 1
1 2 3 4
2 1 3
1 1 3 2

样例输出 #1

2
4
-1
1