문제

동물의 숲에서는 일요일마다 무를 살 수 잇고, 그 후 일주일 동안 너굴 상점에 무를 팔아 시세 차이를 이용해 수익을 낼 수 있다. 그러나 일주일이 지나게 되면 무가 전부 썩어버려 더이상 팔 수 없게 된다. 동물의 숲에서 부자의 삶을 실현하고 싶던 지원이는 무트코인의 애용자였다.

지원이는 무를 팔 때 현재 시세가 높아도 더 높아지지 않을까 기대하며 끝까지 팔지 않고 있다가 무가 전부 썩어버리기 마련이였다. 이에 기분이 나빴던 지원이는 평소에 코딩을 잘하여 동물의 숲의 코드를 고쳐 무가 썩기까지의 시간을 $N$일로 늘리는데 성공하였다. 그러나 여전히 지원이는 무를 팔지 못하고 시세가 더 높이지기를 기다리는 습관이 도져서 큰 수익을 올리지 못하고 있었다. 여러분들이 지원이를 위해 지원이가 원하는 수익 이상을 낼 수 있도록 도와주는 프로그램을 작성해보자.

너굴 상점은 앞으로 $N$일 동안의 무 가격 정보를 관리하고 있다. 하지만 지원이가 무 유통기한을 늘리는 과정에서 실수로 다른 코드도 같이 바꿔버려 시세 예측이 자주 바뀌게 되었다. 즉, 어떤 날의 무 가격이 변칙적으로 바뀔 수도 있다.

지원이는 어떤 날 $s$에 무를 샀을 때, 적어도 $K$벨 이상의 이익을 낼 수 있는 가장 늦은 날에 팔고 싶어 한다.

시세가 바뀌는 상황에서 여러분들은 두 종류의 연산을 처리하는 프로그램을 지원이를 위해 짜보도록 하자. 연산은 다음과 같이 주어진다.

• 연산 $A$ $1$ $i$ $x$ : $i$ 번째 날의 무 가격을 $x$로 변경한다.

• 연산 $B$ $2$ $s$ $K$ : $s$ 번째 날에 무를 샀다고 했을 때 $s$번째 날 이후의 날들 중에서, 무 가격이 $P_s + K$ 이상이 되는 가장 늦은 날의 번호를 출력한다. 만약 그러한 날이 존재하지 않으면 $-1$을 출력한다.

입력

첫째 줄에 두 정수 $N$, $Q$ 가 공백으로 구분되어 주어진다.

둘째 줄에 $N$개의 정수 $P_i$ 가 공백으로 구분되어 주어진다. $P_i$ 는 $i$번째 날의 무 가격을 의미한다.

이후 $Q$개의 줄에 걸쳐 연산 $A$와 연산 $B$중 하나가 한 줄에 하나씩 주어진다.

$1 \leq N, Q \leq 200\,000$

$1 \leq P_i \leq 10^9$

$1 \leq i, s \leq N$

$1 \leq x \leq 10^9$

$1 \leq K \leq 10^9$

출력

각 $B$번 연산에 대해, 조건을 만족하는 가장 늦은 날의 번호를 한 줄에 하나씩 줄력한다.

예제 입력 1

7 5
90 80 85 110 95 140 70
2 2 20
1 3 120
2 2 20
2 5 40
2 7 1

예제 출력 1

6
6
6
-1