#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;
        in >> N >> M;
        FILE * f = fopen("aib.in","r");
        int vec[N+1];
        for(int i = 1; i <= N; i++)
                in >> vec[i];
        int *BitTree = createTree(vec,N);
        int nr,a,b;
        char gar[100];
        fgets(gar,sizeof(gar),f);
        fgets(gar,sizeof(gar),f);
        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;
}