#![allow(dead_code)]
#![allow(unused_variables)]
use rcin::RInStream;
use std::fs::{self, File};

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 main() {
    // Reading
    let file = File::open("aib.in").unwrap();
    let mut reader = RInStream::from_file(file);

    let n = reader.read::<usize>().unwrap();
    let m = reader.read::<usize>().unwrap();

    let mut v: Vec<i32> = (0..n).map(|_| reader.read::<i32>().unwrap()).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 reader.read::<usize>().unwrap() {
        0 => {
            add_update(
                &mut aib,
                &mut v,
                reader.read::<usize>().unwrap(),
                reader.read::<i32>().unwrap(),
            );
            None
        }

        1 => Some(sum_query(
            &aib,
            &v,
            reader.read::<usize>().unwrap(),
            reader.read::<usize>().unwrap(),
        )),
        _ => Some(min_query(&aib, &v, reader.read::<i32>().unwrap(), 1)),
    });

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