import java.io.BufferedReader;
import java.io.FileNotFoundException;
import java.io.FileReader;
import java.io.IOException;
import java.io.PrintWriter;
import java.io.UnsupportedEncodingException;


public class BIT {
	
	int[] tree;
	int n;
	
	public BIT(int n){
		this.n = n;
		tree = new int[n+1];
	}
	
	void update(int idx ,int val){
	    while (idx <= n){
	        tree[idx] += val;
	        idx += (idx & -idx);
	    }
	}
	
	int sum(int id){
		
		int s = 0;
		while(id>0){
			s += tree[id];
			id -= (id & -id);
		}
		return s;
	}
	
	int search(int key,int lower,int upper){
		int mid = lower + (upper - lower)/2;
		if(upper >= lower){
			if((mid == 0 || key>sum(mid-1)) && key == sum(mid) )
				return mid;
			else if(key > sum(mid))
				return search(key,mid+1,upper);
			else
				return search(key,lower,mid-1);			
		}	
		return -1;
	}

	public static void main(String[] args) throws FileNotFoundException, UnsupportedEncodingException{
		
		BufferedReader br = null;
		PrintWriter writer = new PrintWriter("aib.out","UTF-8");
		
		try{
    		br = new BufferedReader(new FileReader("aib.in"));
    		String currentLine = br.readLine();
    		String[] numbers = currentLine.split(" ");
    		int n = Integer.parseInt(numbers[0]);
    		int m = Integer.parseInt(numbers[1]);
    		
    		BIT b = new BIT(n);
    		
    		currentLine = br.readLine();
    		String[] str = currentLine.split(" ");
    		for(int i = 0; i<n; ++i){
    			b.update(i+1,Integer.parseInt(str[i]));    			
    		}
    		
    		while((currentLine = br.readLine()) != null){
    			str = currentLine.split(" ");
    			if(Integer.parseInt(str[0]) == 0){
    				b.update(Integer.parseInt(str[1]),Integer.parseInt(str[2]));
    			}
    			else if(Integer.parseInt(str[0]) == 1){
    				writer.print(b.sum(Integer.parseInt(str[2])) - b.sum(Integer.parseInt(str[1])));
    			}
    			else if(Integer.parseInt(str[0]) == 2){
    				writer.print(b.search(Integer.parseInt(str[2]),1,n));
    			}
    		}
    		
    	}
    	catch (IOException e) {
			e.printStackTrace();
		} finally {
			try {
				if (br != null)br.close();
			} catch (IOException ex) {
				ex.printStackTrace();
			}
		}
		
		writer.close();

	}

}