题目背景

仓库管理员最常被问的一句话是："东西到底在哪个架子上？"盘点时他关心的不是总共有多少货，而是从左侧第一个货架开始往上加，加到第几个架子才够数。

题目描述

仓库里有一排货架，从左到右编号 $1,2,\dots,n$，第 $i$ 个货架上放着 $a_i$ 件货物。接下来要对货架进行 $m$ 次操作，操作有两种：

• 1 x v：把第 $x$ 个货架上的货物数量改为 $v$；
• 2 S：查询最小的货架编号 $p$，使得前 $p$ 个货架上的货物总数不少于 $S$。若全部货架上的货物总数仍然少于 $S$，输出 -1。

输入格式

第一行两个整数 $n, m$。

第二行 $n$ 个整数 $a_1,a_2,\dots,a_n$。

接下来 $m$ 行，每行形如 1 x v 或 2 S，含义如上。

输出格式

对每一次 2 操作输出一行一个整数表示答案。

输入输出样例 #1

输入 #1

5 6
1 2 3 4 5
2 6
1 3 0
2 6
2 100
1 5 100
2 15

输出 #1

3
4
-1
5

说明

样例解释

初始货物总数依次为 $1,3,6,10,15$，前 $3$ 个货架正好凑够 $6$。把第 $3$ 个货架清空后，需要前 $4$ 个货架才够 $6$；此时总数为 $12$，因此查询 $100$ 无解。最后把第 $5$ 个货架改成 $100$，前 $5$ 个货架凑出 $107\ge 15$。

数据范围

• 对于 $100\%$ 的数据，$1\le n,m\le 5\times 10^5$，$0\le a_i,v\le 10^9$，$1\le S\le 10^{18}$。
• 保证操作中出现的 $x$ 满足 $1\le x\le n$。