use std::{
    fs::{self, File},
    io::{BufRead, BufReader},
};

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) -> i32 {
    if s == 0 {
        return a as i32 - 1;
    }
    if s < 0 || a >= aib.len() {
        return -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 fin(path: &str) -> impl Iterator<Item = String> {
    let file = File::open(path).unwrap();
    let reader = BufReader::new(file);

    reader.lines().flat_map(|line| {
        line.unwrap()
            .split_whitespace()
            .map(str::to_string)
            .collect::<Vec<_>>()
    })
}

fn next<T: std::str::FromStr>(iter: &mut impl Iterator<Item = String>) -> T {
    iter.next().unwrap().parse::<T>().ok().unwrap()
}

fn main() {
    // Reading
    let mut reader = fin("aib.in");

    let n: usize = next(&mut reader);

    let m = next(&mut reader);

    let mut v: Vec<i32> = (0..n).map(|_| next(&mut reader)).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 results = (0..m).flat_map(|_| match next(&mut reader) {
        0 => {
            add_update(&mut aib, &mut v, next(&mut reader), next(&mut reader));
            None
        }

        1 => Some(sum_query(&aib, &v, next(&mut reader), next(&mut reader))),
        _ => Some(min_query(&aib, &v, next(&mut reader), 1)),
    });

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