#include <cstdio>
#include <cstdlib>
#include <cmath>
using namespace std;


#define nmax 100010

int AIB[nmax], X, N, M, A, B, C;

void Update(int pos, int val)
{
     for(; pos <= N; pos += (pos & (-pos)))
           AIB[pos] += val;
}

int Query(int pos)
{
     int sum = 0;
     for(; pos; pos -= (pos & (-pos)))
           sum += AIB[pos];
     return sum;
}

int BS(int val)
{
     int left = 1, right = N, mid;
     while(left <= right)
     {
                mid = (left + right) >> 1;
                if(Query(mid) == val) return mid;
                if(Query(mid) < val) left = mid + 1;
                if(Query(mid) > val) right = mid - 1;
     }
     return -1;
}


int main()
{
    freopen("aib.in", "r", stdin);
    freopen("aib.out", "w", stdout);
    int i;
    scanf("%i %i", &N, &M);
    for(i = 1; i <= N; i++)
    {
          scanf("%i", &X);
          Update(i, X);
    }
    for(; M; M --)
    {
          scanf("%i", &C);
          if(C == 0)
          {
               scanf("%i %i", &A, &B);
               Update(A, B);
          }
          if(C == 1)
          {
               scanf("%i %i", &A, &B);
               printf("%i\n", Query(B) - Query(A - 1));
          }
          if(C == 2)
          {
               scanf("%i", &A);
               printf("%i\n", BS(A));
          }
    }
    return 0;
}