题目描述

S校的同学中有几个同学做操特别爱偷懒，但是老师们却一直看着他们让他们不能愉快地偷懒。

今天n位同学排成一列在操场上做操，从前到后分别给他们标号为1,2,3,…,n，每位同学做操都有一个认真值a[i]，他们知道老师有一个容忍值w，如果一位同学要偷懒，他周围的同学就必须认真做操，否则老师会生气，具体的来说，如果一位同学A位于i位置，另一位同学B位于j位置，他们两想要偷懒，而他们中间的同学都在认真做操，那么必须满足他们中间所有同学做操的认真值和大于等于老师的容忍值，老师才不能生气，也就是a[i+1]+a[i+2]+…+a[j-2]+a[j-1]≥w。同时，随着做操bgm的变化，同学的认真值a[i]会变化，老师的容忍值也会变化。

同学们需要你求出在某个时刻，同学x想要偷懒，他后面的第一位能偷懒的同学是谁。

输入格式

输入第一行为两个正整数n,m，表示学生人数和操作的次数，

第二行有n个数，表示一开始每位学生的认真值，

接下来有m行，每行一个操作，包括操作类型和操作的内容： 操作类型1：格式为1 x v，表示第x位同学的认真值变为v， 操作类型2：格式为2 x w，表示在老师的容忍值为w的情况下，询问第x同学后面的第一位能偷懒的同学的编号，需要保证他们中间的同学认真值之和≥w。

输出格式

对于每个2类型的询问，输出一行一个数，表示对应询问的答案，如果x同学后面没有能够偷懒的同学，输出0.

输入样例

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

输出样例

4 5 4 5 4

说明 第一次1操作后变为：1 2 5 4 5 第二次1操作后变为：1 1 5 4 5

数据说明

对于30%的数据，n,m≤100； 对于60%的数据，n,m≤1000； 对于100%的数据，n,m≤100000，1≤a[i],v≤1000，0≤w≤1000000000。