#include <fstream>
#include <iostream>
#include <string.h>
#include <stdio.h>

using namespace std;

ifstream in("aib.in");
ofstream out("aib.out");

int getParent(int index){
        return index - (index & -index);
}

int getNext(int index){
        return index + (index & -index);
}

int getSum(int vec[],int index){

        int sum = 0;
        while(index > 0) {
                sum += vec[index];
                index = getParent(index);
        }
        return sum;
}

void UpdateValue(int vec[],int index, int val,int dim){
        while(index <= dim) {
                vec[index] += val;
                index = getNext(index);
        }
}

// int *createTree(int vec[],int dim )
// {
//         int *BitTree = new int[dim+1];
//
//         for(int i = 1; i <= dim+1; i++ ) {
//                 BitTree[i] = 0;
//         }
//         for(int i = 1; i <= dim; i++) {
//                 UpdateValue(BitTree,i,vec[i],dim);
//         }
//         for(int i = 1; i <= dim; i++) {
//                 cout << BitTree[i] << ' ';
//         }
//         return BitTree;
// }
int poz(int BitTree[],int n,int cautat)
{
        int st = 1, dr = n,rez = -1,mij,x;
        while(st <= dr)
        {
                mij = (dr + st)/2;
                x = getSum(BitTree,mij);
                if(x == cautat)
                {
                        rez = mij;
                        dr = mij -1;
                }
                else {
                        if(x > cautat)
                                dr = mij - 1;
                        else
                                st = mij + 1;
                }
        }
        return rez;
}
int main()
{
        int M,N;
        FILE * f = fopen("aib.in","r");
        fscanf(f,"%d %d\n",&N,&M);
        int BitTree[N+1];
        memset(BitTree,0,sizeof(BitTree));
        int x;
        for(int i = 1; i <= N; i++)
        {
                fscanf(f,"%d ", &x);
                UpdateValue(BitTree,i,x,N);
        }
        int nr,a,b;
        for(int i = 0; i < M; i++)
        {
                fscanf(f,"%d\n",&nr);
                if(nr == 0) {
                        fscanf(f,"%d %d\n",&a,&b);
                        UpdateValue(BitTree,a,b,N);
                }
                else if (nr == 1)  {
                        fscanf(f,"%d %d\n",&a,&b);
                        out << getSum(BitTree,b) - getSum(BitTree,a-1) << '\n';
                }
                else {
                        fscanf(f,"%d\n",&a);
                        out << poz(BitTree,N,a) <<'\n';
                }
                if(nr != 2)
                        cout << nr <<' '<< a <<' '<< b <<'\n';
                else
                        cout << nr <<' '<< a <<'\n';
        }

        return 0;
}