题目描述

给定一个长度为 $n$ 的数列 $a_1, a_2, \dots, a_n$，你需要处理 $m$ 次操作。操作分为两种：

1. 修改：将 $a_x$ 的值改为 $v$。
2. 查询：给定一个区间 $[l, r]$ 和一个整数 $k$，请你找出在区间 $[l, r]$ 内，第一个大于 $k$ 的数的位置（即最小的下标 $i$ 满足 $l \le i \le r$ 且 $a_i > k$）。如果区间内不存在这样的数，请输出 $-1$。

输入格式

第一行包含两个整数 $n, m$，分别表示数列长度和操作次数。
第二行包含 $n$ 个整数，表示初始数列 $a_1, a_2, \dots, a_n$。
接下来 $m$ 行，每行描述一个操作，格式如下：

• 1 x v：表示将 $a_x$ 修改为 $v$。
• 2 l r k：表示查询区间 $[l, r]$ 内第一个大于 $k$ 的数的位置。

输出格式

对于每个查询操作，输出一行一个整数，表示第一个大于 $k$ 的数的位置；若不存在则输出 $-1$。

样例

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

1
1
2

数据范围与提示

• 对于 $100\%$ 的数据：$1 \le n, m \le 10^5$，$1 \le x, l, r \le n$，$l \le r$，$1 \le a_i, v, k \le 10^9$。
• 保证所有数值在 C++ int 范围内