#!/usr/bin/env python3

import sys

sys.stdout = open('aib.out', 'w')

with open('aib.in', 'r') as f:
    readInts = lambda: map(int, f.readline().split())

    N, M = tuple(readInts())
    bit = [0] * (N + 1)

    def update(i, v):
        while i <= N:
            bit[i] += v
            i += i & -i

    def sum(i):
        s = 0
        while i > 0:
            s += bit[i]
            i -= i & -i
        return s

    def query(i, j):
        return sum(j) - sum(i - 1)

    def findSumPos(s):
        p, pos = 1 << 20, N
        while p > 0:
            if pos - p >= 1 and bit[pos - p] >= s:
                pos -= p
            p >>= 1
        return pos if bit[pos] == s else -1

    for i, v in enumerate(readInts()):
        update(i + 1, v)

    for _ in range(M):
        op = tuple(readInts())
        if op[0] == 0:
            update(*op[1:])
        elif op[0] == 1:
            print(query(*op[1:]))
        else:
            print(findSumPos(op[1]))