#![allow(dead_code)]
#![allow(unused_variables)]
use std::{
    fs::{self, File},
    io::{BufRead, BufReader},
};

#[derive(Debug)]
enum Op {
    Add(usize, i32),
    Sum(usize, usize),
    Min(i32),
}

fn add_update(aib: &mut Vec<i32>, v: &mut Vec<i32>, a: usize, val: i32) {
    v[a] += val;
    let mut i = a;
    while i < aib.len() {
        aib[i] += val;
        let level = ((i as i32 * -1) & (i as i32)) as usize;
        i += level;
    }
}

fn sum_query(aib: &Vec<i32>, v: &Vec<i32>, a: usize, b: usize) -> i32 {
    let mut i = b;
    let mut s = 0;
    while i >= a {
        let level = ((i as i32 * -1) & (i as i32)) as usize;
        if i + 1 - level >= a {
            s += aib[i];
            i -= level;
        } else {
            s += v[i - 1];
            i -= 1;
        }
    }
    s
}

fn min_query(aib: &Vec<i32>, v: &Vec<i32>, s: i32, a: usize) -> usize {
    if s == 0 {
        return a - 1;
    }
    let mut i = a;
    let mut last_i = i;
    while aib[i] <= s {
        last_i = i;
        let level = ((i as i32 * -1) & (i as i32)) as usize;
        i += level;
        if i >= aib.len() {
            break;
        }
    }
    min_query(aib, v, s - aib[last_i], last_i + 1)
}

fn main() {
    // Reading
    let file = File::open("aib.in").unwrap();
    let mut input = BufReader::new(file);
    let mut buf = "".to_owned();
    input.read_line(&mut buf).unwrap();
    let mut first = buf.split_whitespace();
    let n = first.next().unwrap().parse::<usize>().unwrap();
    let m = first.next().unwrap().parse::<usize>().unwrap();

    buf.clear();
    input.read_line(&mut buf).unwrap();
    let mut v: Vec<i32> = buf
        .split_whitespace()
        .map(|x| x.parse::<i32>().unwrap())
        .collect();

    buf.clear();
    let ops: Vec<Op> = (0..m)
        .map(|_| {
            buf.clear();
            input.read_line(&mut buf).unwrap();
            let line: Vec<usize> = buf
                .split_whitespace()
                .map(|x| x.parse::<usize>().unwrap())
                .collect();
            match line[0] {
                0 => Op::Add(line[1], line[2] as i32),
                1 => Op::Sum(line[1], line[2]),
                _ => Op::Min(line[1] as i32),
            }
        })
        .collect();

    // Construction
    let mut aib: Vec<i32> = vec![0; n + 1];
    for i in 1..n + 1 {
        let level = (i as i32 * -1) & (i as i32);
        aib[i] += v[i - 1];
        if i + level as usize <= n {
            aib[i + level as usize] += aib[i];
        }
    }

    // Queries
    let result = ops.iter().flat_map(|op| match *op {
        Op::Add(a, val) => {
            add_update(&mut aib, &mut v, a, val);
            None
        }
        Op::Sum(a, b) => Some(sum_query(&aib, &v, a, b)),
        Op::Min(s) => Some(min_query(&aib, &v, s, 1) as i32),
    });

    // Writing
    let output: String = result.map(|r| format!("{}\n", r)).collect();
    fs::write("aib.out", output).unwrap();
}