#include <bits/stdc++.h>
#define Nmax 150005
#define lsb(x) x & (-x)
using namespace std;

ifstream f("aib.in");
ofstream g("aib.out");

int N, M;
int aib[Nmax];

void update(int pos, int val) {
   for (int i = pos; i <= N; i += lsb(i))
      aib[i] += val;
}
int calc(int pos) {
   int ans = 0;
   for (int i = pos; i > 0; i -= lsb(i))
       ans += aib[i];
   return ans;
}
int bs(int sum) {
   int ans = -1, le = 1, ri = N;
   while (le <= ri) {
       int mid = (le + ri) / 2;
       if (calc(mid) < sum) le = mid + 1;
       else {
          ri = mid - 1;
          if (calc(mid) == sum) ans = mid;
       }
   }

    return ans;
}
int main()
{
    f >> N >> M;
    for (int i = 1; i <= N; ++i) {
        int x;
        f >> x;
        update(i, x);
    }

    for (int i = 1; i <= M; ++i) {
        int tip, x, y;
        f >> tip >> x;
        if (tip < 2) f >> y;

        if (tip == 0) update(x, y);
        if (tip == 1) g << calc(y) - calc(x - 1) << '\n';
        if (tip == 2) g << bs(x) << '\n';
    }

    return 0;
}